图论及其算法23207new.doc

第五章 图 图论﹝Graph?Theory﹞是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有某种关系。实际生活中的很多事例都可用图来表示其内部关系。构建图并应用相关的算法解决一些实际问题是本章的出发点。? 5.1.1图的基本概念 1.图：图是由顶点集合及顶点间的关系集合组成的一种数据结构 Graph＝( V, E ) 其中V = { x | x ∈ 某个数据对象} 是顶点的有穷非空集合；E = {(x, y) | x, y ∈ V } 或E = {x, y | x, y ∈ V Path (x, y)} 是顶点之间关系的有穷集合，也叫做边集合。Path (x, y)表示从 x 到 y 的一条单向通路, 它是有方向的。 有向图与无向图：在有向图中，顶点对x, y是有序的。在无向图中，顶点对(x, y)是无序的。 完全图： 若有 n 个顶点的无向图有 n(n-1)/2 条边, 则此图为完全无向图。有 n 个顶点的有向图有n(n-1) 条边, 则此图为完全有向图。 4.顶点的度： 一个顶点v的度是与它相关联的边的条数。在有向图中, 顶点的度等于该顶点的入度与出度之和。顶点 v 的入度是以 v 为终点的有向边的条数, 顶点 v 的出度是以 v 为始点的有向边的条数。 G＝(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1, vp2, …, vpm，到达顶点vj。则称顶点序列 ( vi vp1 vp2 ... vpm vj ) 为从顶点vi 到顶点 vj 的路径。 6.路径长度：非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。 7.简单路径：若路径上各顶点 v1,v2,...,vm 均不互相重复, 则称这样的路径为简单路径。 8.回路： 若路径上第一个顶点 v1 与最后一个顶点vm 重合, 则称这样的路径为回路或环。 9.连通图与连通分量 在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。非连通图的极大连通子图叫做连通分量。 10.强连通图与强连通分量： 在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。 5.1.2 图的存储 图的存储方法常用的有邻接矩阵和邻接表两种方法，对于数据量比较小的情况下，常用邻接矩阵，数据量大的情况下采用邻接表。 1.邻接矩阵 在图的邻接矩阵表示法中：　 用邻接矩阵表示顶点间的相邻关系　用一个顺序表来存储顶点信息设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：????? const maxn=100; var v:array[1..maxn] of Boolean; {顶点信息} a:array[1..maxn,1..maxn] of integer;{邻接矩阵} 2.邻接表 　图的邻接表表示法类似于树的孩子链表表示法。对于图G中的每个顶点vi，该方法把所有邻接于vi的顶点vj链成一个带头结点的单链表，这个单链表就称为顶点vi的邻接表 邻接表的结点结构 2 f 3 f 4 f 2 3 4 ^ 4 1 ^ 1 4 ^ 1 2 3 ^ (2)邻接表表示： const maxn=100;{邻接表的容量} type tlist=^node; {链接域所属记录类型} node=record t:integer; w:integer; next:tlist; end; type tadv=record {表接点类型} tv:integer; visited:Boolean; link:tlist; end; var a:array[1..maxn] of tadv;{邻接表} 5.2图的遍历 图的遍历是对给定一个图，从其中的任一顶点出发顺序访问图中的所有顶点，每个顶点被访问一次。遍历的结果是将顶点排成一定的序列。图的遍历是求解图的连通、拓扑排序等算法的基础。通常有深度优先遍历和广度优先遍历两种方法