数据结构第7章图

1、第七章 图,7.1 图的定义和术语,7.2 图的存储结构,7.3 图的遍历,作 业,7.1 图的定义和术语,图：是一种非线性数据结构。结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。 顶点：图中的数据元素（如右图的ABCD各点） 有向图：图的顶点偶对之间是有序的（如图） 弧：有向图中，从一个顶点到另一个顶点的有向线段。例如为一弧段，A称为弧尾（初始点），B称为弧头（终段点）。 无向图：图的顶点偶对之间是无序的。,7.1 图的定义和术语,如右图，有向图G1可形式地表示为： G1=(V1，A1) 其中：V1=A, B, C, D A1=,7.1 图的定义和术语,如果以e表示图的边（

2、或弧）的数目，n表示顶点数，那么对于无向图，最多有n(n-1)/2条边。具有n(n-1)/2条边的无向图称为完全图，如右图所示。,对于有向图，最多有n(n-1)条边，则具有n(n-1)条边的有向图称为有向完全图。,具有很少边数的图，称为稀疏图，反之，称为稠密图。,7.1 图的定义和术语,对于无向图G=(V, E),如果边(v,v)E，则称顶点v，v互为邻接点，边（ v，v ）依附于顶点v，v，或者说，该边与顶点v，v相关联。,顶点的度，是和顶点相关的边的数目。,在有向图中，有出度和入度的概念。,7.1 图的定义和术语,无向图中G=(V, E),中从顶点v到顶点v的路径是一个顶点序列，例如右图，

3、 B到C，可以为（B, D, C)。如果是有向图，则路径也是有向的。路径长度是路径上的边或弧的数目。,第一个顶点和最后一个顶点相同的路径称为回路或环（如右图：ACBA)。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。,7.1 图的定义和术语,无向图G中，如果从顶点v到顶点v 有路径，则称v和v 有是连通的。如果对于图中任意两个顶点之间都是连通的，则称G是连通图（右图）。,如右图6，是非连通的，可以分成2个连通分量。,7.1 图的定义和术语,在有向图中，每两个顶点之间如果都存在路径，则称该图为强连通图。,非强连通图中可以

4、分解为几个极大强连通子图，称做有向图的强连通分量。如下图G1，可以分解为两个强连通分量。,7.1 图的定义和术语,生成树 n个顶点的图，只由n-1条边组成的极小连通子图。,生成森林 在有向树中，恰有一个顶点的入度为0，其余顶点的入度为1，则是一棵有向树。 一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，只有足以构成若干棵互不相交的有向树的弧。（书160 图7.6）,7.1 图的定义和术语,图的抽象数据类型定义（书156页）,7.2 图的存储结构,7.2.1数组表示法 用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。其形式描述如下：,#define INF

5、INITY INT_MAX /最大值 #define MAX_VERTEX_NUM 20 /最大顶点个数 typedef enum DG, DN, UDG, UDNGraphkind; /有向图，有向网，无向图，无向网,Typedef struct ArcCell VRType adj; / VRType是顶点关系类型。对无权图，用1或0表示相邻否； 对带权图，则为权值类型 InfoType *info; /该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;,Typedef struct VertexType vexsMAX_VE

6、RTEX_NUM; /顶点向量 AdjMtrix arcs; /邻接矩阵 int vexnum, arcnum; /图的当前顶点数和弧数 GraphKind kind;MGraph; /Kind表示图的种类标志,7.2.1 数组表示法,例如，图G1的邻接矩阵为： 0 1 1 0 0 0 0 1 0 1 0 1 0 0 0 0,7.2图的存储结构,7.2.2 邻接表 对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点 Vi的边（对有向图是以顶点Vi为尾的弧）。每个结点由3个域组成：,表结点,头结点,7.2图的存储结构,7.2.2 邻接表 存储表示： #define MAX_VERT

7、EX_NUM 20 Typedef struct ArcNode int adjvex; /该弧所指向的顶点的位置 struct ArcNode *nextarc;/指向下一条弧的指针 InfoType *info; /该弧相关信息的指针 ArcNode; typedef struct VNode VextexType data; /顶点信息 ArcNode *firstarc; /指向第一条依附该顶点的弧的指针 VNode, AdjListMAX_VERTEX_NUM;,Typedef struct AdjList vertices; /顶点数组 int vexnum, arcnum; /图

8、的当前顶点数和弧数 int kind; /图的种类标志 ALGraph;,（有向图G1）,如果无向图中有n个顶点、e条边，则它的邻接表需n个头结点和2e个表结点。而有向图只需要n头结点，和e个表结点。,7.2.3 十字链表 十字链表可以看成是有向图的邻接表和逆邻接表结合起来得到的一种链表。每一条弧有一个结点，每个顶点也有一个结点。如下图：,例如：P165图7.11,（有向图G1）,有向图的十字链表存储表示,V4,V3,V2,V1,7.2图的存储结构,7.2.4 邻接多重表 邻接多重表是无向图的一种链式存储结构。其结构与十字链表类似。每一条边用一个结点表示，由以下所示的6个域组成：,每一个顶点也

9、用一个结点表示，由如下所示的两个域组成：,例如：P167图7.12,7.3图的遍历,从图中某一顶点出发访问图中其余顶点，且使每一个顶点仅被访问一次。这一过程就叫图的遍历。 图的遍历算法是求解图的连通性问题、拓扑排序和关键路径等算法的基础。,通常有两条遍历图的路径：深度优先搜索和广度优先搜索。,由于图的遍历很复杂，可能在遍历过程中会出现“返回”重复访问的现象，因此，有必要辅设一个数组：visited0.n-1，其初始值都为“假”，但一旦访问之后，便设置为“真”。,7.3图的遍历,7.3.1 深度优先搜索 类似于树的先根遍历，是树的先根遍历的推广。,假设从顶点V1出发进行搜索，在访问了顶点V1之后

10、，选择邻接点V2。因为V2未曾访问，则从V2出发进行搜索。依次类推，接着从V4、V8、V5出发进行搜索。在访问了V5之后，由于V5的邻接点都已被访问，则搜索回到V8。由于同样的理由，搜索继续回到V4、V2直V1，此时由于V1的另一个邻接点未被访问，则搜索又从V1到V3，在继续进行下去。,Bolean visitedMAX; /访问标志 Status (*VisitFunc) (int v); Void DFSTraverse(Graph G, Status(*Visist)(int V) VisitFunc=Visit; for(v=0; vG.vexnum; +v) visitedv=FAL

11、SE; for(v=0; vG.vexnum; +v) if(!visitedv) DFS(G,V); /对尚未访问的顶点调用DFS ,7.3图的遍历,7.3.1 深度优先搜索 整个图的遍历过程可以用以下两个算法来实现,Void DFS(Graph G, int v) Visitedv=TRUE; VisitFunc(v); for(w=FirstAdjVex(G, v): W=0; w=NextAdjvex(G,v,w) if(!visitedw) DFS(G,w);,7.3图的遍历,7.3.1 广度优先搜索,类似于树的按层次遍历的过程。,假设从图中某顶点V出发，在访问了V之后依次访问V的各

12、个未曾访问的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问。,7.3图的遍历,7.3.1 广度优先搜索,广度优先遍历的算法如下所示,Void BFSTraverse(Graph G, Status(*Visit)(int v) for(v=0; v=0; w=NextAdjVex(G, u, w) if(!Visitedw) Visitedw=TRUE; Visit(w); EnQueue(Q, W); ,7.4 图的连通性问题,利用遍历图的算法求解图的连通性问题，重点讨论最小代价生成树的问题。,7.4.1 无向图的连通

13、分量和生成树,对于连通图，从一个顶点出发，即可访问所有顶点；而非连通图，要从多个顶点重新出发，才能访问所有顶点。 例如书159页，图7.3中的图G3是非连通图，深度遍历需3次调用DFS过程。,遍历过程经历边的集合和所有顶点的集合构成一棵生成子树（如下图）,Void DFSForest(Graph G, CSTree for (v=0; vG.vexnum; +v) visitedv=FALSE;,for(v=0; vnextsibling=p; q=p; DFSTree（G,v,p); /建立以p为根的生成树 ,Void DFSTree(Graph G, int v, CSTree first

14、=TRUE;,For(w=FirstAdjVex(G,v); W=0; w=NextAdjVex(G, v,w) if(!visitedw p=(CSTree)malloc(sizeof(CSNode); *p=GetVex(G, w), NULL,NULL; if(first) T-lchild=p; first=FALSE; else q-nextsibling=p; q=p; DFSTree(G, w, q); ,7.4.3 最小生成树,假设要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时，要考虑如何节省经费的问题。（书173页）,可以用连通网来表示n个城市以及n个

15、城市间可能设置的通信线路，其中顶点表示城市，边表示城市之间的线路，边的权值表示相应的代价（如考虑距离，或水、陆地等费用）,对于n个顶点的连通网可以建立许多不同的生成树。需要选择其中代价最小的树，即树的各边的代价之和。,MST性质:假设N=(V,E)是一个连通网，U是顶点集V的一个非空子集。若（u, v）是一条具有最小权值（代价）的边，其中u属于U, v属于V-U, 则必存在一棵包含边（u, v）的最小生成树。,普里姆算法是利用MST性质构造最小生成树的算法：,假设N=(V,E)是一个连通网，TE是N上最小生成树中边的集合。算法从U=u0, TE= 开始，重复执行下述操作：在所有u属于U，v属于

16、V-U的边（u, v）（属于E）找一条代价最小的边（ u0 , v0）并入集合TE，同时v0并入U, 直至U=V为止。此时TE中必有n-1条边，则T=(V,TE)为最小生成树。,书174页 图7.16,Void MiniSpanTree_PRIM(MGraph G, VerTexType u) /用普里姆算法从第u个顶点出发构造网G的最小生成树T,Struct /定义从顶点集U到V-U的代价最小的边的辅助数组 VertexType adjvex; VRType lowcost; closedgeMAX_VERTEX_NUM;,k=LocateVex(G, u);,for(j=0; jG.vex

17、num; +j) if(j!=k) closedgej=u, G.arcskj.adj;,Closedgek.lowcost=0;,for(i=1; iG.vexnum; +i) k=minimum(closedge); printf(closedgek.adjvex, G.vexsk); closedgek.lowcost=0; for(j=0; jG.vexnum; +j) if(G.arcskj.adjclosedgej.lowcost) closedgej=G.vexsk, G.arcskj.adj ,7.5 有向无环图及其应用,一个无环的有向图称作有向无环图。 有向无环图是描述一项工

18、程或系统的进行过程的有效工具。在工程活动中，涉及两放面的问题： 工程进行的前后关系 整个工程要完成的时间问题,7.5.1拓扑排序,描述一个施工流程图，或一个产品流程图。可用图来表示其先后关系，在此有向图中，用顶点表示活动，用弧表示活动间的优先关系（简称AOV网） 。,例如本专业的部分课程（只供参考），按排时存在先后关系。用AOV网来表示，如下图：,有两个拓扑序列:（1）C1C2C4C5C9C12C7C3C13C10C11C6C8 (2) C9C10C11C6C8C12C1C2C4C5C7C3C13,7.5.1拓扑排序,进行上述拓扑排序的方法是： （1）在有向图中选一个没有前驱的顶点且输出之；

19、（2）从图中删除该顶点和所有以它为尾的弧。 （3）重复上述（1）（2）两步，直至全部顶点都输出，或者当前图中不存在无前驱的顶点为止（图中存在环的情况）。,例如下图：,V6,即其拓扑序列为：V1V2V4V3V5V6,Status ToplgSort(ALGraph G) /G采用邻接表存储结构。如果G无回路，输出它的一个顶点拓序列,FindInDegree(G, indegree); /对各点求入度indegree0.vernum-1,Initstack(S);,for(i=0; iG.vexnum; +i) if(!indegreei) Push(S, i); /入度为0者进栈,Count=0

20、; /对顶点记数 While(!StackEmpty(S) Pop(S, i); printf(i, G.verticesi.data); +count; /输出i号顶点并记数 for(p=G.verticesi.firstarc; p; p=p-nextarc) k=p-adjvex; /对i号顶点的每个邻接点的入度减1 if(!(- -indegreek) push(S, k); /如果入度为0，则入栈 ,if(countG.vexnum) return ERROR; /该图有回路 else return OK;,7.5.2关键路径,用顶点表示事件，用弧表示活动，权表示活动持续的时间，称为

21、AOE网。,AOE网中路径长度最长的路径叫做关键路径。（例：书183页图7.29：v1v2v5v8v9）,求关键路径的步骤: (1)顺向求每个顶点的最早发生时间(ve)（取大的值，例如：上图D值的为7，不是6）； (2)逆向求每个顶点的最迟发生时间(vl)（取小的值，例如：上图C的值为2，不是4）; (3)求每条弧的最早发生时间（ee）与最迟发生时间(el)； (4)找最早发生时间与最迟发生时间相等的弧，即为关键路径。,求关键路径的算法： （1）建立AOE网的存储结构； （2）从源点v0出发，令ve0=0, 按拓扑有序求其余各顶点的最早发生时间vei。如果得到的拓扑有序序列中顶点个数小于网中顶

22、点数,则说明网中存在环，不能求关键路径，算法终止，否则继续第（3）步； （3）从汇点vn出发，令vln-1=ven-1, 按逆拓扑有序求其余各顶点的最迟发生时间vli; (4)根据各顶点的ve和vl值，求每条弧s的最早开始时间ee(s)和最迟开始时间el(s)。满足ee(s)=el(s)的为关键路径中的弧。,求关键路径算法：,Status ToplgOrder(AlGraph G, Stack /初始化,While(!StackEmpty(S) Pop(S, j); Push(T, j); +count;,for(p=G.verticesj.firstarc; p; p=p-nextarc)

23、k=p-adjvex; if(- -indegreek= =0) Push(S, k),If(vej+*(p-info)vek) vek=vej+* (p-info); ,if(countG.vexnum) return ERROR; else return OK;,Status CriticalPath(ALGraph G) /G为有向网，输出G的各项关键活动,if(!ToplgOrder(G, T) return ERROR; vl0.G.vexnum-1=veG.venum-1; /各顶点最迟发生时间，先赋值为最大值：活动总时间,While(!StackEmpty(T) ) /逆向求顶点的Vl值 for(Pop(T, j), p= G.verticesj.firstarc; p; p=p-nextarc) k=p-adjvex; dut=*(p-info); if(vlk-dutvlj) vlj=vlk-dut;,for(j=0; jnextarc) k=p-adjvex; dut=*(p-info); ee=vej; el=vlk-du