第7章 图.ppt

1、第7章 图,学习要点: 熟悉图的各种存储结构及其构造算法 了解实际问题的求解效率与采用何种存储结构和算法的密切联系 熟练掌握图的两种搜索路径的遍历：深度优先搜索和广度优先搜索 应用图的遍历算法求解各种简单路径问题，如关键路径、最短路径等,7.1 图的定义和基本术语,7.1.1 图的定义 图形结构： 较线性表和树更为复杂的数据结构。 结点之间的关系是任意的，图中任意两个数据元素都可能相关。 图的结构定义： 图：是由一个顶点集 V 和一个顶点间的关系集合组成的数据结构。 Graph = (V , VR) 其中，V = x | x 某个数据对象，是顶点的有穷非空集合；,VR = (x, y) | x

2、, y V 或 VR = | x, y V 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; / 边/弧的信息 (关系的邻接矩阵) int vexnum, arc

3、num; / 顶点数，边/弧数 GraphKind kind; / 图的种类标志 MGraph;,借助于邻接矩阵容易求得顶点的度： 在无向图中,统计第i行(列)1的个数可得顶点i的度。 即： 在有向图中 统计第i行1的个数可得顶点i的出度; 统计第j列1的个数可得顶点j的入度。,TD(v1)=2 TD(v6)=3,OD(v1)=2 ID(v1)=1 则， TD(v1)=2+1=3,网的邻接矩阵：,Status createUDN(Mgraph ,7.2.2 图的邻接表存储表示 只存储图中已有的弧或边的信息： 对图中的每个顶点都建立一个单链表来存储所有依附于该顶点的弧或边。 无向图：第i个单链表

4、中的结点表示依附于顶点vi的边。 有向图：第i个单链表中的结点表示以顶点vi为尾的弧。 对图中所有顶点使用一个一维数组来存放 单链表中每个结点由三个域组成 邻接点域(adjvex):指示与顶点vi邻接的点在图中的位置； 链域(nextarc):指示下一条边或弧的结点； 数据域(info):存储和边或弧相关的信息，如权值等。,C语言类型描述： 表(弧/边)结点： typedef struct ArcNode int adjvex; / 依附于该边的另一顶点(弧头)的位置 struct ArcNode *nextarc; / 指向下一条弧的指针 InfoType *info; / 该弧相关信息的指

5、针 ArcNode; 头结点： typedef struct VNode VertexType data; / 顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM;,adjvex nextarc info,data firstarc,图的结构定义： typedef struct AdjList vertices; int vexnum, arcnum; int kind; / 图的种类标志 ALGraph;,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,

6、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 C D E,3,0,3,4,2,0,0 1 2 3 4,有向图的 逆邻接表,链表中结点的个数就是该顶点的 出度！,7.2.3 有向图的十字链表存储表示 将有向图的邻接表和逆邻接表结合起来的一种链表。 从横向上看是邻接表，从纵向上看是逆邻接表。,A B C,0 1 2,0 2 ,0 1,2 1 ,2 0 ,C语言类型描述： typedef struct ArcBox / 弧的结构表示 int tailvex,

7、 headvex; InfoType *info; struct ArcBox *hlink, *tlink; VexNode;,弧的结点结构,弧尾顶点位置 弧头顶点位置 弧的相关信息,指向下一个有相同弧尾的结点,指向下一个有相同弧头的结点,typedef struct VexNode / 顶点的结构表示 VertexType data; ArcBox *firstin, *firstout; VexNode;,顶点的结点结构,顶点信息数据,指向该顶点的第一条入弧,指向该顶点的第一条出弧,data,firstin,firstout,有向图的结构表示(十字链表)： typedef struct

8、VexNode xlistMAX_VERTEX_NUM; / 顶点结点(表头向量) int vexnum, arcnum; /有向图的当前顶点数和弧数 OLGraph; 只要输入n个顶点的信息和e条弧的信息，便可建立该有向图的十字链表。,Status CreateDG(OLGraph +k) /输入各弧并构造十字链表 ,scanf( /若弧含有相关信息，则输入 特点： 容易求得顶点的出度和入度。 建立十字链表的时间复杂度和建立邻接表是相同的。,7.2.4 无向图的邻接多重表存储表示 为了便于在搜索无向图的过程中对边进行操作，常采用无向图的邻接多重表作为存储结构。 边的结点结构： typedef

9、 struct Ebox VisitIf mark; / 访问标记 int ivex, jvex; /该边依附的两个顶点的位置 struct EBox *ilink, *jlink; InfoType *info; / 该边信息指针 EBox;,顶点的结构表示： typedef struct VexBox VertexType data; EBox *firstedge; / 指向第一条依附该顶点的边 VexBox; 无向图的结构表示： typedef struct / 邻接多重表 VexBox adjmulistMAX_VERTEX_NUM; int vexnum, edgenum; AML

10、Graph; 邻接多重表和邻接表的差别： 同一条边在邻接表中用两个结点表示； 在邻接多重表中只用一个结点。,7.3 图的遍历,从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。 7.3.1 深度优先搜索 连通图的深度优先搜索遍历： 从图中某个顶点v0出发，访问此顶点，然后依次从v0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v0有路径相通的顶点都被访问到。,以某个顶点的邻接顶点数作为循环控制,例如：W1、W2和W3均为V的邻接点，SG1、SG2和 SG3分别为含顶点W1、W2和W3的子图。 访问顶点 V; for (W1、W2、W3 ) 若该邻

11、接点W未被访问， 则从它出发进行深度 优先搜索遍历。 可见： 深度优先搜索遍历连通图的过程类似于树的先根遍历； 如何判别V的邻接点是否被访问？ 解决的办法是：为每个顶点设立一个“访问标志 visitedw”。,V,w1,SG1,SG2,SG3,w2,w3,w2,算法描述： void DFS(Graph G, int v) / 从顶点v出发，深度优先搜索遍历连通图 G visitedv = TRUE; VisitFunc(v); for(w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G,v,w) if (!visitedw) DFS(G, w); / 对v的尚未

12、访问的邻接顶点w递归调用DFS / DFS,非连通图的深度优先搜索遍历： 首先，将图中每个顶点的访问标志设为 FALSE；然后，搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。 算法描述： void DFSTraverse(Graph G, Status (*Visit)(int v) / 对非连通图 G 作深度优先遍历。 VisitFunc = Visit; for (v=0; vG.vexnum; +v) visitedv = FALSE; / 访问标志数组初始化 for (v=0; vG.vexnum; +v) if (!visitedv)

13、 DFS(G, v); / 对尚未访问的顶点调用DFS ,以图中包含的顶点数作为循环控制,例如：,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,访问标志:,访问次序:,深度优先遍历图的实质：对每个顶点查找其邻接点的过程！,7.3.2 广度优先搜索 对连通图，从起始点V到其余各顶点必定存在路径。,其中，V-w1, V-w2, V-w8 的路径长度为1;,V-w7, V-w3, V-w5 的路径长度为2;,V-w6, V-w4 的路径长度为3。,w1,V,w2,w7,w6,w3,w8,w5,w4,广度优先遍历图的实质：通过边或弧找邻接点

14、的过程！,从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。 算法描述： void BFSTraverse(Graph G, Status (*Visit)(int v) for (v=0; vG.vexnum; +v) visitedv = FALSE; /初始化访问标志 InitQueue(Q); / 置空的辅助队列Q for ( v=0; vG.vexnum; +v ) if ( !visitedv) / v 尚未访问 . / BFSTraverse,说明：使

15、“先被访问的顶点的邻接点”先于“后被访问 的顶点的邻接点”被访问，因此，采用队列来存放已 被访问过的顶点！,visitedv = TRUE; Visit(v); / 访问v EnQueue(Q, v); / v入队列 while (!QueueEmpty(Q) DeQueue(Q, u); / 队头元素出队并置为u for(w=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G,u,w) if ( ! visitedw) visitedw=TRUE; Visit(w); EnQueue(Q, w); / 访问的顶点w入队列 / if / while,课后作业,P47

16、：7.3 2. 假设图G采用邻接表存储，设计一个算法，输出图G中从顶点u到v的所有简单路径。,7.4 图的连通性问题,7.4.1 无向图的连通分量和生成树 对非连通图的遍历，需从多个顶点出发进行搜索。而每一次从一个新顶点出发搜索得到的顶点序列就是图的各个连通分量中的顶点集。 例如：非连通图G3如下,按照P171图7.14所示的邻接表进行深度优先搜索： 第一次调用DFS函数从A出发，得到序列： ALMJBFC 第二次调用DFS函数从D出发，得到序列： DE 第三次调用DFS函数从G出发，得到序列： GKHI,G3的三个连通分量：,A,B,L,M,C,F,J,I,D,E,G,H,K,生成森林,总结

17、：求解生成森林 (1)从第一个未被访问的顶点出发，深度 优先遍历图，并记录顶点之间的边； (2)从其他未被访问的顶点出发，重复(1)， 直至所有顶点被访问。,以孩子兄弟链表作生成森林的存储结构，则可以形成非连通图的生成森林。 void DFSForest(MGraph g, CSTree v+) if(!visitedv) /第v顶点为新的生成树的根结点 . /* if */ /* for */ /* End of DFSForest() */,p = (CSNode *)malloc(sizeof(CSNode); /分配根结点 p-data = GetVex(g, v); /给该结点赋值

18、p-firstChild = NULL; p-nextSibling = NULL; if(!p) T = p; /是第一棵生成树的根(T的根) else q-nextSibling = p; /是其它生成树的根(前一棵的根的“兄弟”) q = p; /q指示当前生成树的根 DFSTree(g, v, p); /建立以p为根的生成树,void DFSTree(MGraph g, int v, CSTree *T) /从第V个顶点出发深度优先遍历图G,建立以T为根的生成树。 visitedv = TRUE; first = TRUE; q = T; for(w = FirstAdjVex(g,

19、v); w!=-1; w = NextAdjVex(g, v, w) if(!visitedw) . /* if */ /* for */ ,p = (CSTree)malloc(sizeof(CSNode); p-data = GetVex(g, w); p-firstChild = NULL; p-nextSibling = NULL; if(first) /W是V的第一个未被访问的邻接顶点 (*T)-firstChild = p; /是根的左孩子结点 first = FALSE; else /W是V的其它未被访问的邻接顶点 q-nextSibling = p; q = p; DFSTre

20、e(g, w, q); /从第W个顶点出发深度优先遍历图G，建立子生成树q。,对连通图进行搜索时，搜索过程中经历的所有边和图中所有的顶点构成了连通图的一个极小连通子图，即连通图的生成树。 深度优先生成树： 广度优先生成树：,1,3,4,2,5,1,3,4,2,5,1,3,4,2,5,生成树的特点： n个顶点的连通子图的生成树是一个极小连通子图，它包含图中所有顶点和n-1条边(但有n-1条边的图不一定是生成树)。 生成树中任意两个顶点间的路径是唯一的。 注：边数n-1时，则形成环；边数n-1时则不连通。 对于非连通图，其中的每一个连通分量都可以通过遍历得到一棵生成树，所有这些连通分量的生成树就构

21、成了非连通图的生成森林。,7.4.2 有向图的强连通分量 深度优先搜索求有向图G的强连通分量步骤： 在G上，从某个顶点出发沿以该顶点为尾的弧进行深度优先搜索遍历，并按其所有邻接点的搜索都完成的顺序将顶点排列起来。对DFSTraverse函数修改： 在入口处加上count=0； 在结束之前加上finished+count=v。 在G上，从最后完成搜索的顶点(即finishedvexnum-1中的顶点)出发，沿着以该顶点为头的弧做逆向的深度优先搜索遍历，直至有向图中所有顶点都被访问为止。对DFSTraverse修改： 第二个循环语句的边界条件改为v从finishedvexnum-1至finishe

22、d0。 则，每一次调用DFS作逆向深度优先遍历所访问到的顶点集就是有向图G中一个强连通分量的顶点集。,例如：,V1,V2,V3,V4,V1,V2,V3,V4,0,1,0,2,2,0,2,3,3,0,3,1,3,2,0 1 2 3,finished：,1,3,2,0,1,2,3,0 1 2 3,2,3,V1：v1, v3, v4,V2：v2,7.4.3 最小生成树 问题： 假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？ 该问题等价于： 构造网的一棵最小生成树，即：在e条带权的边中选取n-1条边(不构成回路)，使“权值之

23、和”为最小。 使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。,构造最小生成树的准则： 必须使用且仅使用该连通图的n-1条边连接图中的n个顶点； 不能使用产生回路的边； 各边上的权值的总和达到最小。,最小生成树(MST)性质： 假设N(V,E)是一个连通网，U是顶点集V的一个非空子集，若(u,v)是一条具有最小权值的边，其中uU, vV-U,则必存在一棵包含边(u,v)的最小生成树。 普里姆(Prim)算法： 基本思想： 第一步：取图中任意一个顶点 v 作为生成树的根； 第二步：往生成树上添加新的顶点w。顶点w和已经在生成树上的顶点v之间必定存在一条边，

24、并且该边的权值在所有连通顶点v和w之间的边中取值最小； 第三步：继续往生成树上添加顶点，直至生成树上含有 n 个顶点为止。,MST性质,例如：,a,e,d,c,b,g,f,14,8,5,3,16,21,所得生成树权值和,= 14+8+3+5+16+21 = 67,图解构造算法：,1,2,3,4,5,6,1,2,3,4,5,6,1,6,5,1,2,3,4,5,6,1,6,5,5,7,5,4,1,2,3,4,5,6,1,5,5,5,4,6,2,6,5,1,5,7,5,4,2,6,3,U=1, V-U=2, 3, 4, 5, 6,U=1, 3, V-U=2, 4, 5, 6,U=1, 3, 6, V

25、-U=2, 4, 5,1,2,3,4,5,6,1,5,5,5,4,6,2,1,2,3,4,5,6,1,5,5,4,6,2,1,2,3,4,5,6,1,5,5,4,6,2,1,2,3,4,5,6,1,5,5,4,6,2,3,3,U=1, 3, 6, V-U=2, 4, 5,U=1, 3, 6, 4, V-U=2, 5,U=1, 3, 6, 4, 5, V-U=2,U=1, 3, 6, 4, 2, V-U=5,由上述图解算法的过程知，构造的最小生成树不一定唯一，但最小生成树的权值之和一定是相同的。,1,2,3,4,5,6,1,5,4,2,1,2,3,4,5,6,1,5,4,2,3,3,1,2,3,

26、4,5,6,6,5,1,5,7,5,4,2,6,3,添加的顶点应满足下列条件： 在生成树的构造过程中，图中n个顶点分属两个集合： 已落在生成树上的顶点集 U； 尚未落在生成树上的顶点集V-U。 应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。,设置一个辅助数组closedge，对当前V-U集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边： struct VertexType adjvex; / U集中的顶点序号 VRType lowcost; / 边的权值 closedgeMAX_VERTEX_NUM;,例如：,a,e,d,c,b,a,a,a,19,14,18,14,e,12,e,e,8,16,8,d,3,d,d,7,21,3,c,5,5,0,1,2,3,4,5,6,16,g,21,f,U=a,V-U=b, c, d, e, f, g,算法描述： void MiniSpanTree_P(MGraph G, VertexType u) /用普里姆算法从顶点