图的定义和术语

单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第七章 图,7.1,图的定义和术语,7.2,图的存储结构,7.2.1,数组表示法,7.2.2,邻接表,7.3,图的遍历,7.3.1,深度优先搜索,7.3.2,广度优先搜索,7.4,图的连通性问题,7.4.3,最小生成树,7.5,有向无环图及其应用,7.5.1,拓扑排序,7.6,最短路径,7.6.1,从某个源点到其余各顶点的最短路径,7.6.2,每一对顶点之间的最短路径,7.1,图的,定义和术语,图的定义：,是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继。图是由顶点集合,(,vertex),及顶点间的关系集合组成的一种数据结构：,Graph(V,R),其中,V=v|v,某个数据对象,是顶点的有穷非空集合；,R=VR=(v,w)|v,w,V,基本术语：,1.有向图与无向图,在有向图中，顶点对,是有序的。在无向图中，顶点对,(,x,y),是无序的。有向边又可称为,弧,中,vi,称为,弧尾,或初始点，,vj,称为,弧头,或终端点。,5,3,6,7,2,1,4,有向图,V=1,2,3,4,5,6,7,VR=,无向图,5,3,6,7,2,1,4,V=1,2,3,4,5,6,7,VR=(1,3),(3,4),(4,5),(1,2),(2,6),(2,7),(6,7),(5,6),(1,5),(,1,7),2.邻接点及关联,若无向图中存在边,(,v,u)，,则称顶点,v,和,u,互为邻接点；边,(,v,u),依附于顶点,v,和,u；,或者说边,(,v,u),和顶点,v,和,u,相关联。,3.,顶点的度、入度、出度,在无向图中：顶点,V,的度,=,与,V,相关联的边的数目,在有向图中：,顶点,V,的出度,=,以,V,为狐尾的有向边数,顶点,V,的入度,=,以,V,为狐头的有向边数,顶点,V,的度,=,V,的出度,+,V,的入度,V0,V4,V3,V1,V2,V0,V1,V2,V3,4.路径、回路,无向图,G=（V，E）,中的顶点序列,v,1,v,2,v,k,若,(,v,i,v,i+1,),E(i=1,2,k-1),v=v,1,u=,v,k,则称该序列是从顶点,v,到顶点,u,的路径。若,v=u，,则称该序列为回路。,在图,G1,中，,V0,V1,V2,V3,是,V0,到,V3,的路径。,V0,V1,V2,V3,V0,是回路。,V0,V4,V3,V1,V2,例：,例：有向图,G2,V0,V1,V2,V3,在图,G2,中，,V0,V2,V3,是,V0,到,V3,的路径。,V0,V2,V3,V0,是回路。,有向图,G=（V，E）,中的顶点序列,v,1,v,2,v,k,若,E (i=1,2,k-1),v=v,1,u=,v,k,则称该序列是从顶点,v,到顶点,u,的路径。若,v=u，,则称该序列为回路。,在一条路径中,若除起点和终点外,所有顶点各不相同,则称该路径为简单路径。,由简单路径组成的回路称为简单回路。,在图,G1,中，,V0,V1,V2,V3,是,简单路径。,V0,V1,V2,V4,V1,不是简单路径。,在图,G2,中，,V0,V2,V3,V0,是简单回路。,无向图,G1,有向图,G2,V0,V4,V3,V1,V2,V0,V1,V2,V3,5.简单路径和简单回路,非连通图,连通图,强连通图,非强连通图,V0,V1,V2,V3,V0,V4,V3,V1,V2,V0,V1,V2,V3,V0,V2,V3,V1,V5,V4,6.连通图（强连通图）,在无（有）向图,G=(V,E),中，若对任何两个顶点,v、u,都存在从,v,到,u,的路径，则称,G,是连通图（强连通图）。,(a),(b),(c),V0,V4,V3,V1,V2,V0,V4,V3,V1,V2,V0,V4,V3,V1,V2,8.子图,设有两个图,G=（V，E）、G1=（V1，E1），,若,V1,V，E1,E，,则称,G1,是,G,的子图。例,:(,b)、(c),是,(,a),的子图,7.权,某些图的边具有与它相关的数,称之为权。这种带权图叫做网络。,9.连通分量（强连通分量）,V0,V2,V3,V1,V5,V4,无向图,G,的极大连通子图称为,G,的连通分量。极大连通子图意思是：该子图是,G,连通子图，将,G,的任何不在该子图中的顶点加入，子图不再连通。,V0,V2,V3,V1,V5,V4,连通分量,非连通图,有向图,G,的极大强连通子图称为,G,的强连通分量。极大强连通子图意思是：该子图是,G,的强连通子图，将,D,的任何不在该子图中的顶点加入，子图不再是强连通的。,强连通分量,V0,V1,V2,V3,V0,V2,V3,V1,10.权与网,图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。,带权的图称为,网,。,极小连通子图：该子图是,G,的连通子图，在该子图中删除任何一条边，子图不再连通,包含无向图,G,所有顶点的极小连通子图称为,G,的生成树,对非连通图，则称由各个连通分量的生成树的集合为非连通图的生成森林。,连通图,G1,G1,的生成树,V0,V4,V3,V1,V2,V0,V4,V3,V1,V2,V0,V4,V3,V1,V2,11.生成树和生成森林,例：,G1,2,4,1,3,7.2.1,数组表示法,邻接矩阵：,表示顶点间相联关系的矩阵。,定义：,设,G=(V,E),是有,n,1,个顶点的图，,G,的邻接矩阵,A,是具有以下性质的,n,阶方阵,：,例：,1,5,3,2,4,G2,网的邻接矩阵可定义为：,例：,1,4,5,2,3,7,5,3,1,8,6,4,2,邻接矩阵类型定义,:,#,define INFINITY INT_MAX,#define MAX_VERTEX_NUM 20,typedef,enumDG,DN,AG,AN,GraphKind,;,typedef,struct,ArcCell,VRType,adj,;,InfoType,*info;,ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM,typedef,struct,VertexType,vexsMAX_VERTEX_NUM,;,AdjMatrix,arcs;,int,vexnum,arcnum,;,GraphKind,kind;,MGraph,;,邻接表的类型定义,#,define MAX_VERTEX_NUM 20,typedef struct ArcNode,int adjvex;,struct ArcNode*nextarc;,InfoType*info;,ArcNode;,7.2.2,邻接表,实现：为图中每个顶点建立一个单链表，第,i,个单链表中的结点表示依附于顶点,V,i,的边（有向图中指以,V,i,为尾的弧）。,typedef struct VNode,VertexType data;,ArcNode*firstarc;,VNode,AdjListMAX_VERTEX_NUM;,typedef struct,AdjList vertices;,int vexnum,arcnum;,int kind;,ALGraph;,adjvex,nextarc,vexdata,firstarc,例：,G1,b,d,a,c,1,2,3,4,a,c,d,b,vexdata,firstarc,3,2,4,1,adjvex,nextarc,例：,a,e,c,b,d,G2,1,2,3,4,a,c,d,b,vexdata,firstarc,4,2,1,2,adjvex,nextarc,5,e,4,3,5,1,5,3,2,3,例：,G1,b,d,a,c,1,2,3,4,a,c,d,b,vexdata,firstarc,4,1,1,3,adjvex,nextarc,逆邻接表：有向图中对每个结点建立以,V,i,为弧头的弧的单链表。,7.3,图的遍历,7.3.1,深度优先搜索,方法：从图的某一顶点,V0,出发，访问此顶点；然后依次从,V0,的未被访问的邻接点出发，深度优先遍历图，直至图中所有和,V0,相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点,重复上述过程，直至图中所有顶点都被访问为止,。,V1,V2,V4,V5,V3,V7,V6,V8,例：,深度遍历：,V1,V2 V4 V8 V5 V3 V6 V7,深度优先遍历算法（递归算法）参见,P169。,V1,V2,V4,V5,V3,V7,V6,V8,深度优先生成树,V1,V2,V4,V5,V3,V7,V6,V8,深度优先遍历算法（递归算法）,Boolean visitedMAX;,Status(*VisitFunc)(int v);,void DFSTraverse(Gragh G,Status(*Visit)(int v),VisitFunc=Visit;,for(v=0;vG.vexnum;+v)visitedv=FALSE;,for(v=0;v=0;w=NextAdjVex(G,v,w),if(!visitedw)DFS(G,W);,V1,V2,V4,V5,V3,V7,V6,V8,例：,1,2,3,4,1,3,4,2,vexdata,firstarc,2,7,8,3,adjvex,nextarc,5,5,6,4,1,5,1,2,8,2,6,7,8,6,7,8,7,3,6,3,5,4,深度遍历：,V1,V3,V7,V6,V2,V5,V8,V4,7.3.2,广度优先搜索,方法：从图的某一顶点,V0,出发，访问此顶点后，依次访问,V0,的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点,，,重复上述过程，直至图中所有顶点都被访问为止。,广度优先遍历算法,void BFSTraverse(Graph G,Status(*Visit)(int v),for(v=0;vG.vexnum;+v)visitedv=FALSE;,InitQueue(Q);,for(v=0;v=0;w=NextAdjVex(G,u,w),Visitedw=TRUE;visit(w);,EnQueue(Q,w);,V1,V2,V4,V5,V3,V7,V6,V8,例,:,广度遍历：,V1,V2 V3 V4 V5 V6 V7 V8,V1,V2,V4,V5,V3,V7,V6,V8,广度优先生成树,V1,V2,V4,V5,V3,V7,V6,V8,例,:,1,4,2,3,5,1,2,3,4,1,3,4,2,vexdata,firstarc,5,5,4,3,adjvex,nextarc,5,5,1,5,1,1,4,3,2,2,广度遍历序列：,1 4 3 2 5,7.4,图的连通性问题,问题提出：要在,n,个城市间建立通信联络网，用顶点表示城市；权表示城市间建立通信线路所需花费代价。希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小,最小,(,代价,),生成树。,1,6,5,4,3,2,7,13,17,9,18,12,7,5,24,10,7.4.3,最小生成树,算法思想：设,N=(V,E),是连通网，,TE,是,N,上最小生成树中边的集合。,1.,初始令,U=u0,(u0,V),TE=。,2.,在所有,uU,vV-U,的边(,u,v)E,中，找一条代价最,小的边(,u0,v0)。,3.,将(,u0,v0),并入集合,TE，,同时,v0,并入,U。,4.,重复上述操作直至,U=V,为止，则,T=(V,TE),为,N,的最,小生成树。,方法一：普里姆,(,Prim),算法,构造最小生成树的方法,例：,1,6,5,4,3,2,6,5,1,3,5,6,6,4,2,5,1,3,1,1,6,3,1,4,1,6,4,3,1,4,2,1,1,6,4,3,2,1,