《第7章 图n幻灯片课件》由会员分享,可在线阅读,更多相关《第7章 图n幻灯片课件(110页珍藏版)》请在金锄头文库上搜索。
1、第七章 图,7.1 抽象数据类型图的定义,7.2 图的存储表示,7.3 图的遍历,7.4 最小生成树,7.5 重(双)连通图和关节点,7.6 拓扑排序,7.7 关键路径,学习目标 掌握图的概念、存储结构、操作实现及算法复杂度; 掌握图的深度、广度优先搜索遍历算法; 掌握图的生成树概念,普里姆算法、克鲁斯卡算法。 掌握图的拓扑排序方法,图是由一个顶点集 V 和一个弧集 R构成的数据结构。 Graph = (V , R ) 其中,VR| v,wV 且 P(v,w) 表示从 v 到 w 的一条弧,并称 v 为弧头,w 为弧尾。 谓词 P(v,w) 定义了弧 的意义或信息。,图的结构定义:,若VR 必
2、有VR, 则称 (v,w) 为顶点v 和顶点 w 之间存在一条边。,B C A D F E,由顶点集和边集构成的图称作无向图。,例如: G2=(V2,VR2) V2=A, B, C, D, E, F VR2=, , , , , , ,名词和术语,网、子图,完全图、稀疏图、稠密图,邻接点、度、入度、出度,路径、路径长度、简单路径、简单回路,连通图、连通分量、 强连通图、强连通分量,生成树、生成森林,A,B,E,C,F,A,E,F,B,B,C,设图G=(V,VR) 和图 G=(V,VR), 且 VV, VRVR, 则称 G 为 G 的子图。,15,9,7,21,11,3,2,弧或边带权的图分别称作
3、有向网或无向网。,假设图中有 n 个顶点,e 条边,则,含有 e=n(n-1)/2 条边的无向图称作完全图;,含有 e=n(n-1) 条弧的有向图称作 有向完全图;,若边或弧的个数 enlogn,则称作稀疏图,否则称作稠密图。,假若顶点v 和顶点w 之间存在一条边, 则称顶点v 和w 互为邻接点,,A,C,D,F,E,例如:,ID(B) = 3,ID(A) = 2,边(v,w) 和顶点v 和w 相关联。 和顶点v 关联的边的数目定义为边的度。,B,顶点的出度: 以顶点v为弧尾的弧的数目;,A,B,E,C,F,对有向图来说,,顶点的入度: 以顶点v为弧头的弧的数目。,顶点的度(TD)= 出度(O
4、D)+入度(ID),例如:,ID(B) = 2,OD(B) = 1,TD(B) = 3,设图G=(V,VR)中的一个顶点序列 u=vi,0,vi,1, , vi,m=w中,(vi,j-1,vi,j)VR 1jm, 则称从顶点u 到顶点w 之间存在一条路径。 路径上边的数目称作路径长度。,A,B,E,C,F,如:长度为3的路径A,B,C,F,简单路径:序列中顶点不重复出现的路径。,简单回路:序列中第一个顶点和最后一个顶点相同的路径。,若图G中任意两个顶点之间都有路径相通,则称此图为连通图;,若无向图为非连通图,则图中各个极大连通子图称作此图的连通分量。,B,A,C,D,F,E,B,A,C,D,F
5、,E,若任意两个顶点之间都存在一条有向路径,则称此有向图为强连通图。,A,B,E,C,F,A,B,E,C,F,对有向图,,否则,其各个强连通子图称作它的强连通分量。,假设一个连通图有 n 个顶点和 e 条边,其中 n-1 条边和 n 个顶点构成一个极小连通子图,称该极小连通子图为此连通图的生成树。,对非连通图,则称由各个连通分量的生成树的集合为此非连通图的生成森林。,B,A,C,D,F,E,结构的建立和销毁,插入或删除顶点,对邻接点的操作,对顶点的访问操作,遍历,插入和删除弧,基本操作,CreatGraph( / 若G中存在顶点u,则返回该顶点在 / 图中“位置” ;否则返回其它信息。,Get
6、Vex(G, v); / 返回 v 的值。,PutVex( / 对 v 赋值value。,对邻接点的操作,FirstAdjVex(G, v); / 返回 v 的“第一个邻接点” 。若该顶点 /在 G 中没有邻接点,则返回“空”。,NextAdjVex(G, v, w); / 返回 v 的(相对于 w 的) “下一个邻接 / 点”。若 w 是 v 的最后一个邻接点,则 / 返回“空”。,插入或删除顶点,InsertVex( /在图G中增添新顶点v。,DeleteVex( / 删除G中顶点v及其相关的弧。,插入和删除弧,InsertArc( / 在G中增添弧,若G是无向的, /则还增添对称弧。,D
7、eleteArc( /在G中删除弧,若G是无向的, /则还删除对称弧。,遍 历,DFSTraverse(G, v, Visit(); /从顶点v起深度优先遍历图G,并对每 /个顶点调用函数Visit一次且仅一次。,BFSTraverse(G, v, Visit(); /从顶点v起广度优先遍历图G,并对每 /个顶点调用函数Visit一次且仅一次。,7.2 图的存储表示,一、图的数组(邻接矩阵)存储表示,二、图的邻接表存储表示,Aij=,0 (i,j)VR,1 (i,j)VR,一、图的数组(邻接矩阵)存储表示,B,A,C,D,F,E,定义:矩阵的元素为,有向图的邻接矩阵为非对称矩阵,A,B,E,C
8、,F,网的邻接矩阵可定义为:,v1 v2 v3 v4 v5 v6,v1 v2 v3 v4 v5 v6,typedef struct ArcCell / 弧的定义 VRType adj; / VRType是顶点关系类型。 对无权图,用1或0表示相邻否; 对带权图,则为权值类型。 InfoType *info; / 该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;,typedef struct / 图的定义 VertexType / 顶点信息 vexsMAX_VERTEX_NUM; AdjMatrix arcs; / 弧的信息 i
9、nt vexnum, arcnum; / 顶点数,弧数 GraphKind kind; / 图的种类标志 MGraph;,0 A 1 4 1 B 0 4 5 2 C 3 5 3 D 2 5 4 E 0 1 5 F 1 2 3,B,A,C,D,F,E,二、图的邻接表 存储表示,1 4,2,3,0 1,2,0 1 2 3 4,A B C D E,有向图的邻接表,A,B,E,C,F,可见,在有向图的邻接表中不易找到指向该顶点的弧。,A,B,E,C,D,有向图的逆邻接表,A B C D E,3,0,3,4,2,0,0 1 2 3 4,在有向图的邻接表中,对每个顶点,链接的是指向该顶点的弧。,typed
10、ef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针 ArcNode;,adjvex nextarc info,弧的结点结构,typedef struct VNode VertexType data; / 顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM;,data firstarc,顶点的结点结构,typedef struct AdjList v
11、ertices; int vexnum, arcnum; int kind; / 图的种类标志 ALGraph;,图的结构定义,邻接表与邻接矩阵有什么异同之处?,联系:邻接表中每个链表对应于邻接矩阵中的一行,链表中结点个数等于一行中非零元素的个数。 2. 区别: 对于任一确定的无向图,邻接矩阵是唯一的(行列号与顶点编号一致),但邻接表不唯一(链接次序与顶点编号无关)。 邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。 3. 用途: 邻接矩阵多用于稠密图的存储(e接近n(n-1)/2); 而邻接表多用于稀疏图的存储(en2),7.3 图的遍历,从图中某个顶点出发游历图,访遍
12、 图中其余顶点,并且使图中的每个顶点 仅被访问一次的过程。,深度优先搜索,广度优先搜索,遍历应用举例,从图中某个顶点V0 出发,访问此顶点,然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和V0有路径相通的顶点都被访问到。,一、深度优先搜索遍历图,连通图的深度优先搜索遍历,例:,V1,顶点访问次序:,V2,V4,V8,V5,V3,V6,V7,V1,V2,V5,V8,V4,V3,V6,V7,V1,V2,V4,V8,V5,V3,V7,V6,V1,V2,V5,V8,V4,V3,V7,V6,V1,V3,V6,V7,V2,V4,V8,V5,连通图的深度优先遍历类似于树的先根遍历,
13、V,w1,SG1,SG2,SG3,W1、W2和W3 均为 V 的邻接点,SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。,访问顶点 V : for (W1、W2、W3 ) 若该邻接点W未被访问, 则从它出发进行深度优先搜索遍历。,w2,w3,w2,从上页的图解可见:,1. 从深度优先搜索遍历连通图的过程类似于树的先根遍历;,解决的办法是:为每个顶点设立一个 “访问标志 visitedw”。,2. 如何判别V的邻接点是否被访问?,void DFS(Graph G, int v) / 从顶点v出发,深度优先搜索遍历连通图 G visitedv = TRUE; VisitFunc(
14、v); for(w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G,v,w) if (!visitedw) DFS(G, w); / 对v的尚未访问的邻接顶点w / 递归调用DFS / DFS,首先将图中每个顶点的访问标志设为 FALSE, 之后搜索图中每个顶点,如果未被访问,则以该顶点为起始点,进行深度优先搜索遍历,否则继续检查下一顶点。,非连通图的深度优先搜索遍历,void DFSTraverse(Graph G, Status (*Visit)(int v) / 对图 G 作深度优先遍历。 VisitFunc = Visit; for (v=0; vG.v
15、exnum; +v) visitedv = FALSE; / 访问标志数组初始化 for (v=0; vG.vexnum; +v) if (!visitedv) DFS(G, v); / 对尚未访问的顶点调用DFS ,a,b,c,h,d,e,k,f,g,F F F F F F F F F,T,T,T,T,T,T,T,T,T,a,c,h,d,k,f,e,b,g,a,c,h,k,f,e,d,b,g,访问标志:,访问次序:,例如:,0 1 2 3 4 5 6 7 8,a b c d e f g h k,从图中的某个顶点V0出发,并在访问此顶点之后依次访问V0的所有未被访问过的邻接点,之后按这些顶点被访问的先后次序依次访问它们的邻