1、第七章 图,本章内容,定义和术语存储结构：邻接矩阵、邻接表，十字链表，邻接多重表两种遍历策略：深度优先搜索和广度优先搜索连通性和最小生成树拓扑排序和关键路径两类求最短路径问题的解法,本章要点,熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系；熟练掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优先搜索的两种形式(递归和非递归)和广度优先搜索的算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异；应用图的遍历算法求解各种简单路径问题。,7.1 图的定义和术语,图G由两个集合V(G)和E(G)组成，记作G=(V,E) 其中V(G)是顶点的非空有穷
2、集合，E(G)是边的有穷集合，而边是顶点的无序对或有序对。,图的基本术语,顶点(vertex)数据元素所构成的结点通常称为顶点。弧(arc)若两个顶点间有关系E ，则称为一条弧。弧头(又称终端点)若为一条弧，则顶点 y 称为弧头。弧尾(又称初始点)若为一条弧，则顶点 x 称为弧尾。边(Edge)无向图中两条弧和可用一条边(x,y)来表示 。,图的基本术语(续),顶点的度（degree）与顶点相关联的边数称为该顶点的度，又分为入度和出度 。顶点的入度（indegree）以顶点为头的弧数称为该顶点的入度 。顶点的出度（outdegree）以顶点为尾的弧数称为该顶点的出度 。路径（path）由顶点v
3、i经过一系列边和顶点到达顶点vj所得到的顶点序列。回路（loop-又称环 cycle）起点和终点为同一顶点的路径称为回路。,图的基本术语(续),简单路径(路径的顶点)序列中顶点不重复出现的路径。简单回路(简单环) 除路径起点和终点相同外，其余顶点均不相同的回路。稀疏图边数很少的图 (如enlogn)。稠密图边数很多的图。权(weight)有些图的边或弧具有一定的大小，称之为权。网带权值的图又称为网或网络。,图的基本术语(续),子图由图的部分顶点和边组成的新图称为原图的子图。生成子图由图的全部顶点和部分边组成的子图称为原图的生成子图。邻接点若边(vi,vj)E，则 vi与vj互为邻接点。依附若边
4、(vi,vj)E ，则称边(vi,vj)依附于顶点vi和vj。相关联若边(vi,vj)E ，又称边(vi,vj)与顶点vi和vj相关联。,图的基本术语(续),有向图若E ，并不总有E，则称此图为有向图。无向图若E ，总有E，则称此图为无向图。完全图具有 n*(n-1)/2条边的无向图称为完全图。有向完全图具有 n*(n-1)条弧的有向图称为有向完全图。,图的基本术语(续),连通无向图中顶点vi到vj间有路径存在，则称vi和vj是连通的。连通图无向图中任意两顶点间均存在路径，则称该图为连通图。连通分量无向图中的极大连通子图称为原图的连通分量。强连通图有向图中任意两顶点间均存在路径，则称该图为强连
5、通图。强连通分量有向图中的极大强连通子图称为原图的强连通分量。,图的基本术语(续),生成树连通图的极小连通生成子图称为原图的生成树。有向树恰有一个顶点入度为0 ，其余顶点入度均为1的有向图。生成森林由多棵有向树构成的有向图的生成子图称为生成森林。最小代价生成树连通网中由最小权值的边构成的生成树。,图的基本操作,图的生成操作 CreatGraph(&G,V,VR)顶点定位函数 LocateVex(G,v)取顶点数据函数 GetVex(G,v)求第一个邻接顶点函数 FirstAdjVex(G,v)求下一个邻接顶点函数 NextAdjVex(G,v,w)插入顶点操作 InsertVex(&G,v)删
6、除顶点操作 DeleteVex(&G,v)插入边/弧的操作 InsertArc(&G,u,v)删除边/弧的操作 DeleteArc(&G,u,v)图的遍历 Traverse(G),图的存储结构:邻接矩阵,数组表示法邻接矩阵(优缺点),#define Infinity INT_MAXtypedef enumDG, DN, AG, AN GraphKind;typedef struct ArcCell VRType adj; InfoType *info;ArcCell, AdjMatrix2020;typedef struct Gragh VertexType vexs20; int vtxnu
7、m, arcnum; AdjMatrix arcs; GraghKind kind; Gragh;,图的存储结构：邻接矩阵,邻接矩阵(边表)arcs 3 2 4 5 2 ,3,2 5 4,2,A B C D,图的存储结构:关联矩阵,关联矩阵,图的存储结构:邻接表,邻接表(有向图)按结点出度建立;,typedef struct ArcNode int adjvex; InfoType weight; struct ArcNode *nextarc;ArcNode;typedef struct VNode VertexType data; ArcNode *firstarc;VNode, Adjl
8、ist20;typedef struct AdjList vertices; int vexnum;AlGraph;,12,3,2,23,9,16,7,5,链式存储结构(续),逆邻接表 按结点入度建立;,链式存储结构(续),十字链表按结点入度和出度建立；,typedef struct ArcBox int tailvex,headvex; struct ArcBox *hlink,*tlink; ArcBox;typedef struct VexNode VertexType data; ArcBox *firstin,*firstout;VexNode;typedef struct VerN
9、ode xlist20; int vexnum,arcnum;OLGraph;,链式存储结构(续),邻接多重表是无向图的一种存储结构存储无向图用十字链表法的问题,#define MAX_VEX_NUM 20struct EBox EdgeType data; int ivex, jvex; struct EBox *ilink, *jlink;typedef struct VexBox VertexType data; struct EBox *firstedge;VexBox;typedef struct VexBox vexMAX_VEX_NUM; int nvex, nedge;,7.3
10、 图的遍历,图的遍历按某种搜索顺序对图中每个结点访问且仅访问一次。遍历图的两种方式深度优先搜索 DFS广度优先搜索 BFS,深度优先搜索,类似树的先根边历从图中某顶点 v0 出发，访问该顶点依次从v0未被访问过的邻接点中选取一个顶点作为新的出发点，用同样的方法访问其它所有顶点；直到所有与v0 连通的顶点均被访问到为止若仍有顶点未被访问，则从未被访问过的顶点中任意选取一个顶点作为新的出发点；反复此过程，直至图中所有顶点均被访问过一遍为止,A,B,F,E,H,C,D,G,深度优先搜索算法,int visitedMAX;void DFSTraverse (Graph G) for (v = 0; v
11、 G.vexnum; v+) visitedv = 0; /* memset(visited, 0, sizeof(visited) */ for (v = 0; v G.vexnum; v+) if (!visitedv) DFS(G, v);,void DFS( Graph G, int v ) Visit( v ); visitedv = 1; for (w = FirstAdjVex(G,v); w; w = NextAdjVex(G, v, w) if (!visitedw) DFS(G, w);,广度优先搜索,类似树的按层次遍历从某顶点v0出发，访问该顶点依次访问v0的所有未被访问
12、过的邻接点然后将所有这些邻接点作为新的出发点，用同样的方法访问其它所有顶点，直到所有与v0 连通的顶点均被访问到为止；若此时仍有顶点尚未被访问，则从未被访问过的顶点中任意选取一个顶点作为新的出发点；反复此过程，直至图中所有顶点均被访问过一遍为止。,A,B,C,F,H,D,G,E,广度优先搜索算法,void BFSTraverse ( Graph G) memset(visited, 0 , sizeof(visited); InitQueue(Q); for (v = 0; v child = p; else last_sibling-next_sibling = p; last_siblin
13、g = p; DFSTree(G, w, p); ,遍历图构成生成森林算法改写,void DFS_Forest(Graph G) root = NULL; pp = ,遍历图构成生成森林算法改写(续),void DFSTree(Graph G, int v, struct CSNode *t) visitedv = TRUE; pp = t; for (w = FirstAdjVex(G,v); w; w = NextAdjVex(G, v, w) if (visited(w) continue; *pp = p = malloc(sizeof(CSNode); *p = GetVex(G,
14、w), NULL, NULL ; pp = ,遍历图构成生成森林C+算法(1),void DFS_Forest(Graph G) struct CSNode * ,遍历图构成生成森林C+算法(2),void DFSTree(Graph G, int v, struct CSNode * ,最小生成树,定义由一个网络生成的各边的权数总和最小的生成树记为MST性质：设N=(V,E)是一个连通网，U是顶点集V的一个非空子集，若(u,v)uU,vV-U是一条具有最小权值(代价)的边，则必存在一棵包含边(u,v)的最小生成树构造算法Prim算法Kruskal算法,Prim算法,将图中顶点分为两个集合，其
15、中集合 X 包含图的一个顶点 v0，集合 Y 包含除 v0 外的其它所有顶点；将跨接这两个集合的权值最小的边加入图中，并将其依附在集合 Y 中的顶点 v1 从 Y 中移入集合 X 中；反复过程 2，直到集合 Y 为空，所得生成子图即为最小生成树。教材图7.16,结构数组closedge， 数组每元素两个分量adjvex,lowcost算法复杂性O(n2),Prim算法描述,void MinSpanTree_PRIM(MGraph, G, VertexType u) /* cost为NxN矩阵，costij存储节点i到节点的边的权值 */ k = LocateVex(G, u); for (j
16、= 0; j 0节点中挑最小的节点 */ printf(closedgek.adjvex, k); /* 输出边的两个端点的编号 */ closedgek.lowcost = 0; /* k号节点并入已完成集合*/ /* 考虑新加入的节点k, 修正closedge */ for (j = 0; j G.vexnum; j+) if (costkj adjvex; if (-indegreek = 0) push(S,k); return count G.vexnum ? ERROR : ok;,关键路径,源点入度为0的顶点，即工程的开始点；汇点出度为0的顶点，即工程的完成点；关键活动关键路径上
17、的活动，关键活动的加快可以缩短工期；关键路径影响整个工程进度的那些活动所组成的路径减少这些活动所需时间，整个工程就可能提前完成。AOE图 (Activity On Edge)顶点一般用来表示事件(状态)弧用来表示活动弧的权值表示活动所需时间此类有向无环图称AOE图AOE网的性质进入Vi的活动都结束， Vi所代表的事件才能发生顶点Vi所代表的事件发生，从Vi出发的活动才能开始,关键路径的提出,确定关键路径的变量e(i):活动ai的最早开始时间，活动ai的弧尾事件的最早发生时间。l(i):活动ai的最迟开始时间，在不影响总工期的前提下，活动ai最迟必须开始进行的时间。ve(i):事件vi的最早发生
18、时间，从V1到事件Vi的最长路径长度。vl(i):事件vi的最迟发生时间，从Vi到事件Vn的最长路径。关键活动：l(i)=e(i)的活动；,如左图所示工程，其最后完工时间为21天。,能否加快某些活动进度，使整个工期缩短呢？,关键路径的确定,1.公式：设活动 ai = 弧的权定义为活动的持续时间dut()，则有下式成立：e(i) = ve(j)，l(i) = vl(k)-dut()。若e(i) = l(i) ，则活动 ai就是关键路径上的关键活动。,2.求ve(i): 用拓扑排序求各事件的最早发生时间，有：,V1 V2 V3 V4 V5 V6 V7 V8 V9 V10,(a1a2a3) (a4)
19、 (a5a6) (a7) (a8) (a9a10) (a11a13) (a12) (a14),ve：,0,4,3,2,7,8,13,10,15,21,e：,(0 0 0),(4),(3 3),(2),(7),(8 8),(13 13),(10),(15),vl：,0,4,3,4,7,8,13,11,16,21,关键活动： a1、a2、a4、a6 、a8 、a9 、a13；,关键路径： V1V2V5V7V10 和 V1V3V6V7V10 。,21,l：,(0 0 2),(4),(4 3),(4),(7),(8 9),(15 13),(11),(16),21,求关键路径的算法,求关键路径的算法(续
20、),7.6 最短路径,单源最短路径 -迪杰斯特拉(Dijkstra)算法每一对顶点间的最短路径 -弗洛伊德(Floyd)算法,从某点到其余顶点的最短路径,Dijkstra算法（最小路径生成树）（按路径长度递增的次序产生最短路径）从源点的所有邻接点中找出距源点最近的邻接点；以该邻接点为中间点，比较其它各顶点与源点的路径通过中间点后是否更短；若是：用新路径代替老路径，再从中找出其它各点距源点最近的顶点作为新的中间点，这也是该点的最短路径；反复此过程，直至全部顶点距源点的最短路径均找到,例:求图中 v1到各点的最短路径,V1 到各点的最短距离为： 4 、3 、5 和 2；,最短路径：Dijkstra
21、算法,void ShortestPath_DIJ(int v0) for (v = 0; v vexnum; v+) vexv.visted = 0; vexv.distance = arcsv0v; vexv.plink = arcsv0v INFINITY ? 结果：单向链表vexi.plink链为节点i最短路径的逆序， vexi.distance为路径长度,作业(1),设一个无向图含n个节点e条边，分析邻接矩阵和邻接表存储该图的空间复杂度。给出下面无向图的邻接矩阵和邻接表，分别计算两种方法所占用的存储空间(假定所有指针、整数和数据均占4字节)。什么是图的最小代价生成树？分别按Prim算法
22、和Kruscal算法求下图的最小代价生成树。写出从顶点a出发DFS和BFS遍历所得到的顶点序列。,作业(2),含有5个节点A,B,C,D,E的有向图的邻接矩阵： 0 100 30 10 0 60 0 20 10 0 50 0 画出逻辑图，画出图的十字链表存储结构。设以邻接矩阵作为一个有向图的存储结构，编写算法判断该图中是否含有环路？,作业(3),AOV网络和AOE网络中，节点和边分别表示什么？列出下列AOE网络中各个事件的最早发生时间和最迟发生时间，找出关键路径并指出完成该工程所需要的最短时间。,作业(3),利用Dijkstra算法求出下图从顶点V1到其他各个顶点的最短路径和路径长度，写出执行
23、算法过程中各步的状态。,含有N个节点的无向图G用邻接矩阵A存储。对于G中的某节点v，如果从G中删除顶点v以及与顶点v相关联的边之后，G变成由两个或者两个以上的非空连同分量所组成的图，则称v是图G的关节节点。例如右图中只有节点4和6是关节节点，而其他节点都不是。设计在图G中寻找所有关节节点的算法，并且分析所设计算法的时间复杂度，然后，用C语言编写实现这一算法的程序。,作业(4),自选存储结构，编写一算法判断无向图中任意给定的两个顶点间是否存在一条长度等于k的简单路径(即不含回路的路径)。2/5/6/9/10,上机作业(选作),设计邻接表结构存储有向图增加和删除带权的边DFS遍历图最小生成森林及费用给定两顶点，求最短路径长度及途中的节点名,
