4、数据结构_图.ppt

1、,1、图的定义和术语2、图的存储结构3、图的遍历4、图的连通性问题5、有向无环图及其应用6、最短路径,第七章 图,7.1 图的定义和术语,图(Graph)是一种网状数据结构，其形式化定义如下： Graph = (V,R) V = x|xDataObject R = VR VR = x,y|P(x,y)(x,yV) DataObject为一个集合，该集合中的所有元素具有相同的特性。V中的数据元素通常称为顶点，VR是两个顶点之间的关系的集合。 P(x,y)表示x和y之间有特定的关联属性P。 若x,y VR，则表示从顶点x到顶点y的一条弧，并称x为弧尾或起始点，称y为弧头或终端点，此时图中的边是有方

2、向的，称这样的图为有向图。 若x,y VR，必有若y,x VR，即VR是对称关系，这时以无序对(x,y)来代替两个有序对，表示x和y之间的一条边，此时的图称为无向图。,A,B,C,D,A,B,C,D,E,有向图 G1,无向图 G2,结点(顶点),有向边（弧）、弧尾(初始结点)、弧头(终止结点),A,B,A,B,有向图：G1=(V1，E1) V1 = A,B,C,D E1 = , , , ,结点(顶点),边(无向边),A,B,无向图：G2=(V2，E2) V2 = A,B,C,D,E E2 = (A,B), (A,C),(B,D), (B,E）, (C,E),(D,E),A,B,图的抽象数据类型

3、定义：,ADT Graph 数据对象V：一个集合，该集合中的所有元素具有相同的特性。 数据关系R：R = VR VR = x,y|P(x,y)(x,yV) 基本操作： (1)CreateGraph(G) 操作前提：已知图G不存在。 操作结果：创建图G。 (2)LocateVex(G, u); 若G中存在顶点u，则返回该顶点在 图中“位置” ；否则返回其它信息。 (3)TraverseGraph(G) 操作前提：已知图G存在 操作结果：按照某种次序，对图G的每个顶点访问一次且仅访问一次。,基本术语:,完全图、稀疏图和稠密图 设n表示图中顶点的个数，用e表示图中边或弧的数目，并且不考虑图中每个顶点

4、到其自身的边或弧。即若Vi,VjVR,则ViVj。对于无向图而言，其边数e的取值范围是0n(n-1)/2。有n(n-1)/2条边(图中每个顶点和其余n-1个顶点都有边相连)的无向图称为无向完全图。对于有向图而言，其边数e的取值范围是0n(n-1)。有n(n-1)条边(图中每个顶点和其余n-1个顶点都有弧相连)的有向图称为有向完全图。对于有很少条边的图(e A,则称顶点v邻接到顶点v，顶点v邻接自顶点v，或者说弧与顶点v和v相关联。 (4) 度、入度和出度 对于无向图而言，顶点v的度是指和v相关联边的数目，记做TD(v)。在有向图中顶点v的度有出度和入度两部分，其中以顶点v为弧头的弧的数目称为该

5、顶点的入度，记做ID(v)，以顶点v为弧尾的弧的数目称为该顶点的出度，记做OD(v),则顶点v的度为TD(v) = ID(v)+ OD(v)。,(5) 权与网 在实际应用中，图的边或弧往往与具有一定意义的数有关，即每一条边都有与它相关的数，称为权，这些权可以表示从一个顶点到另一个顶点的距离或耗费等信息。这种带权的图称为赋权图或网。 (6) 路径与回路 路径的长度是指路径上经过的弧或边的数目。在一个路径中，若其第一个顶点和最后一个顶点是相同的即v=v，则称该路径为一个回路或环。若表示路径的顶点序列中的顶点各不相同，则称这样的路径为简单路径。除了第一个和最后一个顶点外，其余各顶点均不重复出现的回路

6、称为简单回路。 (7) 连通图 在无向图G=(V,E)中，若从Vi到Vj有路径想通，则称顶点Vi与Vj是连通的。如果对于图中的任意两个顶点Vi、VjV， Vi、Vj都是连通的，则称该无向图G为连通图。无向图中的极大连通子图称为该无向图的连通分量。在有向图G=(V,A)中，若对于每对顶点Vi、VjV且ViVj，从Vi到Vj和从Vj到Vi都有路径，则称该有向图为强连通图。有向图的极大强连通子图称做有向图的强连通分量。一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以连通n个点的n-1条边。,1、邻接矩阵表示法 也称做数组表示法。,A,B,C,D,无权值的有向图的邻接矩阵： 设有向

7、图有n个结点，则用n行n列矩阵A表示有向图； 如果i至j有一条弧，则Ai,j =1；否则，Ai,j=0 注意： Ai,i=0。 出度: i行之和；入度: j列之和。,表示成右图矩阵,0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0,7.2 图的存储结构,图的存储方法有很多，邻接矩阵表示法，邻接表，邻接多重表，十字链表等。由于每种方法各有利弊，因此可以根据实际应用问题来选择合适的存储表示方法。,无权值的无向图的邻接矩阵 设无向图有n个结点，则用n行n列的矩阵A表示该无向图； 如果i至j有一条边,则Ai,j=1 ； 否则，Ai,j=0 注意：Ai,i = 0。 i结点的度: i行或i

8、列之和。 为对称矩阵。,表示成右图矩阵,0 1 1 0 0 1 0 0 1 1 1 0 0 0 1 0 1 0 0 1 0 1 1 1 0,A,B,C,D,E,图的加权邻接矩阵 设图有n个顶点，则用n行n列的矩阵A表示该图； 如果i至j有一条边（弧）且它的权值为w。则 Ai,j=w ;否则，Ai,j= （或其它标志）；,a,b,图的建立（邻接矩阵代码如下）：,int CreateDN(AdjMatrix *G) /*创建一个有向网(带权有向图)*/ int i,j,k,weight; VertexData v1,v2; printf(输入图的顶点数和弧数n); fflush(stdin); s

9、canf(%d,%d, ,int LocateVertex(AdjMatrix *G,VertexData v) /*求顶点位置函数*/ int j=Error,k; for(k=0;kvexnum;k+) if(G-vexsk=v) j=k; break; return(j); ,/*用邻接矩阵法创建有向网的算法如下：*/ #include adjmatrix.h void main() AdjMatrix G; CreateDN( ,/ adjmatrix.h #include stdlib.h #include stdio.h #define MAX_VERTEX_NUM 10 /*最多

10、顶点个数*/ #define INFINITY 0X7FFFFFFF /*表示极大值，即*/ #define True 1 #define False 0 #define Error -1 #define Ok 1 typedef enumDG, DN, UDG, UDN GraphKind; /*图的种类：DG表示有向图, DN表示有向网, UDG表示无向图, UDN表示无向网*/ typedef char VertexData; /*假设顶点数据为字符型*/ typedef struct ArcNode int adj; /*对于无权图，用1或0表示是否相邻；对带权图，则为权值类型*/ A

11、rcNode; typedef struct VertexData vexsMAX_VERTEX_NUM; /*顶点向量*/ ArcNode arcsMAX_VERTEX_NUMMAX_VERTEX_NUM; /*邻接矩阵*/ int vexnum,arcnum; /*图的顶点数和弧数*/ GraphKind kind; /*图的种类标志*/ AdjMatrix; /*(Adjacency Matrix Graph)*/,2、邻接表,设图具有 n 个结点，则用顶点数组表、边（弧）表表示该有向图或无向图。 顶点数组表：用数组存放所有的顶点。数组大小为图顶点数n。 边表（边结点表）：每条边用一个结

12、点进行表示。同一个结点的所有的边形成它的边结点单链表。,数组顶点表中的分量的形式：,data:结点的数据域，保存结点的数据值（比如顶点号）。 firstarc:结点的指针域，给出自该顶点出发的的第一条边（弧）的边结点的地址。,VNode：,边表中的结点的形式,adjvex:结点的数据域，保存结点的数据（比如顶点号）。 nextvex:结点的指针域，给出该结点的下一结点（边）的地址。,info:边结点的数据域，保存边的 权值等。如不是网，此部分可省去。,ArcNode:,实例：,adj,逆邻接表对有向图而言,1,2,3,4,有向图 G1,有向图邻接表建立,void CreateGraph(Adj

13、List *adj) VertexData v, u; int Vnum, Unum; ArcNode2 *q = NULL; printf(输入顶点数和边数(例：6,10):n); scanf_s(%d,%d, ,/求顶点位置函数-邻接表 int LocateVertex2(AdjList *G2, VertexData v) int k, j = Error; for (k = 0; kvexnum2; k+) if (G2-vertexk.data = v) j = k; break; return(j); ,void main() AdjList adj; adj.kind2 = DN

14、; CreateGraph( ,/*.邻接表_存储结构. */ typedef struct ArcNode2 int adjvex; /该弧指向顶点的位置 struct ArcNode2 *nextarc;/指向下一条弧的指针 ArcNode2; typedef struct VertexNode VertexData data; /顶点数据 ArcNode2 *firstarc; /指向该顶点第一条弧的指针 VertexNode; /基于邻接表的图 typedef struct VertexNode vertexN; int vexnum2, arcnum2; /图的顶点数和弧数 Grap

15、hKind kind2; /图的种类标志 AdjList; /*.*/,#include using namespace std; #include #include #define N 20 #define True 1 #define False 0 #define Error -1 #define Ok 1 /图的种类：DG表示有向图, DN表示有向网, UDG表示无向图, UDN表示无向网 typedef enum DG, DN, UDG, UDN GraphKind; /假设顶点数据为字符型 typedef char VertexData;,7.3 图的遍历,图的二种常见的遍历形式：

16、 深度优先搜索 广度优先搜索,1、深度优先（DFS）搜索 访问方式：从图中某顶点v出发： 1）访问顶点v；2）从v的未被访问的邻接点出发，继续对图进行深度优先遍历，若从某点出发所有邻接点都已访问过，退回前一个点继续上述过程，若退回开始点，结束。,遍历：图中顶点访问一次且仅一次。 因为一个顶点可以和其它的任何顶点相邻接，为了避免对一个顶点的重复访问，必须对访问过的顶点加以标记。由于顶点的邻接次序是任意的，因此遍历可能有多种可能。,例： 一种DFS遍历序列： V1 , V2 , V4 , V8 , V5 , V3 , V6 , V7 , V9 , V10 , V12 , V11 当存储结构和算法确

17、定后，遍历序列唯一,int visitedN ; /深度遍历-邻接表 void DFS(AdjList g2, int vo) ArcNode2 *p; printf(%c, g2.vertexvo.data); visitedvo = True; p = g2.vertexvo.firstarc; while (p != NULL) if (!visitedp-adjvex) DFS(g2, p-adjvex); p = p-nextarc; ,/深度遍历 for (int i = 0; i adj.vexnum2; i+) if (!visitedi) DFS(adj,i); ,2、广度（

18、宽度，BFS）优先搜索,1）访问顶点v ； 2）访问同v相邻的所有未被访问的邻接点w1,w2, wk； 3）依次从这些邻接点出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问；,图的广度优先的访问次序： 1、2、11、12、3、6、7、10、4、5、8、9 适用的数据结构：队列,1,2,12,11,3,6,7,10,4,5,8,9,#include /广度遍历-邻接表 void BFS(AdjList g2, int v0) ArcNode2 *p; int vi; queue Q; visitedv0 = True; Q.push(v0); while

19、 (!Q.empty() vi = Q.front(); Q.pop(); printf(%c, g2.vertexvi.data); p = g2.vertexvi.firstarc; while (p != NULL) if (!visitedp-adjvex) visitedp-adjvex = True; Q.push(p-adjvex); p = p-nextarc; ,图的应用 连通图的最小生成树 假设N = (V,E)是一个连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值（代价）的边，其中u属于U,v属于V-U，则必存在一棵包含边(u,v)的最小生成树。 问题：

20、假设要在n个城市之间建立通讯联络图，则联通n个城市只需要建立n-1条线路，如何在最节省经费的前提下建立这个通讯网？ 该问题等价于：构造一棵最小生成树，即：在e条带权的边中选取n-1条（不构成回路），使“权值之和”为最小。 处理方法： *普里姆(prim)算法； *克鲁斯卡尔(kruskal)算法。,普里姆(prim)算法 设图顶点数为n。 设置一个集合U，开始图上任选一点u0加入U 重复以下工作n-1次 a) 在满足uU,vU的所有边中选边权w最小的 b) 将v加入集合U中 c) 输出边u ,v及边上的权 w,1,2,4,3,5,6,1,5,3,4,2,Prim算法构造最小生成树图示,（a）,

21、（b）,（c）,（d）,（e）,（f）,Prim代码如下：,void Prim(AdjMatrix gn,VertexData u) /*从顶点u出发，按普里姆算法构造连通网gn 的最小生成树，并输出生成树的每条边*/ k=LocateVertex(gn, u); closedgek.lowcost=0; /*初始化，U=u */ for(i=0;ign.vexnum;i+) if (i!=k) /*对V-U中的顶点i，初始化closedgei*/ closedgei.adjvex=u; closedgei.lowcost=gn.arcski.adj; for(e=1;e=gn.vexnum-

22、1;e+) /*找n-1条边(n= gn.vexnum) */ k0=Minium(closedge); /* closedgek0中存有当前最小边（u0,v0）的信息*/ u0=closedgek0.adjvex; /* u0U*/ v0=gn.vexsk0; /* v0V-U*/ printf(%d,%d,u0, v0); /*输出生成树的当前最小边（u0,v0）*/ closedgek0.lowcost=0; /*将顶点v0纳入U集合*/ for(i=0;ivexnum;i+) /*在顶点v0并入U之后，更新closedgei*/ if(gn.arcsk0i.adjclosedgei.l

23、owcost) closedgei.lowcost=gn.arcsk0i.adj; closedgei.adjvex=v0; ,克鲁斯卡尔(kruskal)算法 先构造一个只含 n 个顶点、而边集为空的子图，把子图中各个顶点看成各棵树上的根结点，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树合成一棵树，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有 n-1 条边为止。,输入：连通网N = (V, E)，最小生成树边的集合TE =空集 输出：一棵最小生成

24、树T = (V, TE) 步骤： step1.初始：只有n个顶点而无边的非连通图T = (V,TE=)； step2.在E中选择代价最小的边，若该边依附的顶点落在T中不同 的连通分量上，则将此边加入到T的TE集合中，否则舍去此 边而选择下一条代价最小的边； step3.重复step2，直至 T中所有顶点都在同一个连通分量上为止 效率： T(n) = O(eloge)，与n无关（其中n为网中结点个数， e为边的个数）,克鲁斯卡尔(kruskal)算法演示过程-图形演示,(a),(b),(c),(d),(e),(f),克鲁斯卡尔(kruskal)算法演示过程-集合演示,V =v1,v2, v3,

25、v4, v5, v6, TE= ,V =v1,v2, v3, v4, v5, v6, TE= (v1, v3),V =v1,v2, v3, v4, v5, v6, TE= (v1, v3 ), (v4, v6 ) ,V =v1,v2, v3, v4, v5, v6, TE= (v1, v3 ), (v4, v6 ) , (v2, v5 ) ,V =v1,v2, v3, v4, v5, v6, TE= (v1, v3 ), (v4, v6 ) , (v2, v5 ) , (v3, v6 ) ,V =v1,v2, v3, v4, v5, v6, TE = (v1, v3 ),(v3, v6 ),(

26、v4, v6 ),(v2, v3 ),(v2, v5 ) ,（v1，v3） 1 （v4，v6） 2 （v2，v5） 3 （v3，v6） 4 （v1，v4） 5 （v2，v3） 5 （v3，v4） 5 （v1，v2） 6 （v3，v5） 6 （v5，v6） 6,typedef struct Edge int v; int u; int w; edge; typedef struct edge *e; int num; /边数 int nv; /定点数 Graph; int cmp(const void *a,const void *b) /按升序排列 edge * x = (edge *)a;

27、edge * y = (edge *)b; return (x-w)-(y-w); void kruskal(Graph *g) int *x=(int *)malloc(sizeof(int)*g-num);/点所在集合 int i,m,n,c=0; for(i=1;inv;i+) xi=i; qsort(g-e,g-num,sizeof(edge),cmp); for(i=0;inum ,1、AOV-网 用顶点表示活动，边表示活动的优先关系的有向图称为AOV网。,若是图中有向边，则vi是vj的直接前驱；vj是vi的直接后继。若存在一条从vi到vj的路径，则称vi是vj的前驱， vj是vi的

28、后继。 AOV网中不允许有回路，这意味着某项活动以自己为先决条件。,3、拓扑排序：对AOV网络中顶点构造拓扑有序序列的过程。,2、拓扑有序序列： 把AOV网络中各顶点按照它们相互之间的优先关系排列一个线性序列的过程。若vi是vj前驱，则vi一定在vj之前；对于没有优先关系的点，顺序任意。,4、拓扑排序的方法 (1)在有向图中选一个没有前驱的顶点且输出之 (2)从图中删除该顶点和所有以它为尾的弧 重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止(此时说明图中有环）,v1,v5,v4,v3,v2,v6,拓扑排序的结果不是唯一的,5.拓扑排序算法实现 为了能方便的找到结点后继，用

29、邻接表表示图，增加一个数组indegree存对应结点的入度，这样查无前驱的结点转化为查入度为0的结点。,算法描述： （1）把邻接表中入度为0的顶点依此进栈 （2）若栈不空，则 a) 栈顶元素vj退栈并输出； b) 在邻接表中查找vj的直接后继vk，把vk的入度减1；若vk的入度为0则进栈 若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕。,int TopoSort(AdjList G) stack S; int indegreeN = 0; int i, count, k; ArcNode2 *p; FindID(G, indegree); /*求各顶点入度*/ for (i =

30、 0; iadjvex; indegreek-; /*i号顶点的每个邻接点的入度减1*/ if (indegreek = 0) S.push(k); p = p-nextarc; /*while*/ if (countG.vexnum2) return(Error); /*该有向图含有回路*/ else return(Ok); ,#include void FindID(AdjList G, int indegreeN) int i = 0; ArcNode2 *p; for (i = 0; i adjvex+; p = p-nextarc; ,关键路径,2.术语 源点：表示整个工程的开始点（

31、入度为0）。 汇点：表示整个工程的结束点（出度为0）。 活动（有向边）：它的权值定义为活动进行所需要的时间。方向表示事件的优先关系。,1.AOE网(Activity On Edge)带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。在工程上常用来表示工程进度计划。,关键活动：活动余量为0的活动 关键路径：从源点到汇点的最长的一条路径，或者全部由关键活动构成的路径。,事件的最早发生时间（ve(j)）：从源点到j结点的最长的路径。意味着事件最早能够发生的时间。 事件的最迟发生时间（vl(j)）：不影响工程的如期完工，事件j必须发生的时间。,活动的最早开始时间：e(i)=ve(j)

32、 活动的最迟开始时间：l(i)=vl(k) - dut(),活动余量：l(i)-e(i)的差,如何求ve(j)和vl(j)？,求关键路径例子,V1 V2 V3 V4 V5 V6 V7 V8 V9,0 6 4 5 7 7 16 14 18,0 6 6 8 7 10 16 14 18,a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11, ,9,8,7,6,4,5,3,2,1,a2=4,a3=5,a5=1,a6=2,a9=4,a1=6,a4=1,a7=9,a8=7,a10=2,a11=4,9,8,7,6,4,5,3,2,1,a2=4,a3=5,a5=1,a6=2,a9=4,a1=6

33、,a4=1,a7=9,a8=7,a10=2,a11=4,6,0,5,7,7,16,14,4,18,9,8,7,6,4,5,3,2,1,a2=4,a3=5,a5=1,a6=2,a9=4,a1=6,a4=1,a7=9,a8=7,a10=2,a11=4,9,8,7,6,4,5,3,2,1,a2=4,a3=5,a5=1,a6=2,a9=4,a1=6,a4=1,a7=9,a8=7,a10=2,a11=4,9,8,7,6,4,5,3,2,1,a2=4,a3=5,a5=1,a6=2,a9=4,a1=6,a4=1,a7=9,a8=7,a10=2,a11=4,第2步,第1步,第n步,A,J,H,I,G,F,E,

34、C,D,B,K,6,8,10,1,6,3,4,3,1,2,7,12,6,10,5,11,8,6,4,4,9,9,3,21,作业：列出下面AOE-网的关键路径,1 从某个源点到其余各顶点的最短路径（单源最短路径问题）,最短路径,1.问题的提出 用带权的有向图表示一个交通运输网，图中： 顶点表示城市 边表示城市间的交通联系 权表示此线路的长度或沿此线路运输所花的时间或费用等 问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中， 各边上权值之和最小的一条路径最短路径,2. 迪杰斯特拉(Dijkstra)算法思想 按路径长度递增次序产生最短路径,3.所需的辅助数组dist disti(i=1,.n

35、)存放当前从源点V0到顶点i的最短路径长度，其初态为弧 上的权值，若该弧不存在，则为无穷大。,4.算法实现分析 设一个集合U，存放已产生的最短路径的顶点。初始，U只包含源点v0,第一条路：1到2、5、3，6之一。,取disti最小，为3,3加到U中,第二条路：1到2、5、8、6之一。而且，3加到U中后，某些顶点的dist值应调整。,3,如果下一条最短路径到达顶点x,则从源点到x的中间点必定都在U中,反证法：若不成立，则至少有一个中间点u不属于U，如左图,则必定有distu+dutdistx，按算法，较短路径应已产生，即u属于U,6. Dijkstra 算法描述,图用邻接矩阵表示，设置集合U与辅

36、助数组dist， 源点vo图的顶点数为n。 gi,j代表上的权； 不存在，gi,j就为无穷大。 (1) disti= gv0,i i=1,2,.,n (2) U=v0; (3) 下面步骤重复n-1次 a) 选择v使得满足 distv=min distu|uU b) v加到集合U中 U=Uv c) 修改不在集合U中顶点的dist值 distw=mindistw,distv+gv,w|wU,7. Dijkstra 算法,void DJS(AdjMatrix G,int v0) /* pathi中存放顶点i的当前最短路径。disti中存放顶点i的当前最短路径长度*/ int distMAX_VERT

37、EX_NUM = 0 ; char pathMAX_VERTEX_NUMMAX_VERTEX_NUM; int i,t,min,k; for (i = 0; i G.vexnum; i+) /* 初始化disti和path i */ disti = G.arcsv0i.adj; strcpy(pathi ,); if (distiINFINITY) addpath(pathi,G.vexsv0); addpath(pathi, G.vexsi); flagv0 = 1; /* 将v0看成第一个已找到最短路径的终点*/ /*以上部分完成了最短路径长度dist ，路径path的初始化工作*/ for (t = 1; t G.vexnum; t+) /*求v0到其余n-1个顶点的最短路径(n= g.vexnum )*/ min = INFINITY; for (i = 0; i G.vexnum; i+) if (!flagi /* pathi=path