《数据结构——C语言描述》第7章：图

基本概念图的存储结构图的遍历生成树最短路径拓扑排序,第7章图,7.1图的基本概念,图定义图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph(V,E)其中V=x|x某个数据对象是顶点的有穷非空集合；E=(x,y)|x,yV是顶点之间关系的有穷集合，也叫做边(edge)集合。,有向图与无向图若图G中的每条边都是有方向的，则称G为有向图。有向边也称为弧。若图G中的每条边都是没有方向的，则称G为无向图。完全图对有n个顶点的图，若为无向图且边数为n(n-1)/2，则称其为无向完全图；若为有向图且边数为n(n-1)，则称其为有向完全图。邻接顶点若（vi,vj）是一条无向边，则称顶点vi和vj互为邻接点，或称vi和vj相邻接，并称边（vi,vj）关联于顶点vi和vj，或称（vi,vj）与顶点vi和vj相关联。,顶点的度一个顶点v的度是与它相关联的边的条数。记作TD(v)。,顶点v的入度是以v为终点的有向边的条数,记作ID(v);顶点v的出度是以v为始点的有向边的条数,记作OD(v)。,子图设有两个图G(V,E)和G(V,E)。若VV且EE,则称图G是图G的子图。,路径在图G(V,E)中,若存在一个顶点序列vp1,vp2,vpm，使得(vi,vp1)、(vp1,vp2)、.、(vpm,vj)均属于E，则称顶点vi到vj存在一条路径。若一条路径上除了vi和vj可以相同外，其余顶点均不相同，则称此路径为一条简单路径。起点和终点相同的路径称为简单回路或简单环。,图的连通在无向图G中，若两个顶点vi和vj之间有路径存在，则称vi和vj是连通的。若G中任意两个顶点都是连通的，则称G为连通图。非连通图的极大连通子图叫做连通分量。,强连通图与强连通分量在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。,权某些图的边具有与它相关的数,称之为权。这种带权图叫做网络。,1,2,3,5,6,8,7,4,A,B,D,C,E,10,7,9,6,6,7,12,3,15,16,60,30,45,35,80,40,75,权图,生成树一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。,生成林若G是一个不连通的无向图，G的每个连通分量都有一棵生成树，这些生成树构成G的生成森林。,7.2图的存储结构,在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。设图A=(V,E)是一个有n个顶点的图，则图的邻接矩阵是一个二维数组A.Edgenn，定义：无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。,邻接矩阵(AdjacencyMatrix),在有向图中,统计第i行1的个数可得顶点i的出度，统计第j列1的个数可得顶点j的入度。在无向图中,统计第i行(列)1的个数可得顶点i的度。,网络的邻接矩阵,邻接矩阵表示法中图的类型定义：#defineMAXSIZE100/*图的顶点个数*/typedefintdatatype;typedefstructdatatypevexsMAXSIZE；/*顶点信息表*/intedgesMAXSIZEMAXSIZE；*邻接矩阵*/intn，e；/*顶点数和边数*/graph；,2,1,4,3,5,无向图,B,A,D,C,E,有向图,2,1,5,3,4,6,20,30,50,40,70,80,有向权图,邻接矩阵表示法中无向网络的建立算法voidCreate_Graph（graph*ga）inti，j，k，w；printf(请输入图的顶点数和边数：n)；scanf(%d，/*假定g-vexsi为顶点的编号，然后变访问标志为1*/for（j=0；jn；j+）if（g-edgesij=1）！visidj）DFSM（g，j）；,voidDFSL（lkgraph*g，intn）/*邻接表上进行DFS遍历*/pointerp;intj；printf（%dn，g-adlistn.data）；/*访问出发点，输出顶点数据*/visidi=1;/*然后变访问标志为1*/for（p=g-adlistn.first；p!=NULL；p=p-next）if（！visidp-vertex）DFSL（g，p-vertex）；,算法分析,图中有n个顶点，e条边。如果用邻接表表示图，沿链可以找到某个顶点v的所有邻接顶点w。由于总共有2e个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问1次，所以遍历图的时间复杂性为O(n+e)。如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为O(n)，则遍历图中所有的顶点所需的时间为O(n2)。,广度优先搜索BFS(BreadthFirstSearch),广度优先搜索的示例,广度优先搜索过程广度优先生成树,使用广度优先搜索在访问了起始顶点v之后，由v出发，依次访问v的各个未曾被访问过的邻接顶点w1,w2,wt，然后再顺序访问w1,w2,wt的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，如此做下去，直到图中所有顶点都被访问到为止。广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。,为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。与深度优先搜索过程一样，为避免重复访问，需要一个辅助数组visited，给被访问过的顶点加标记。,广度优先搜索算法voidBFS（graph*g，intv）/*v是出发顶点的序号，按广度优先搜索法遍历图g，采用邻接矩阵存储结构，BFS遍历*/intj，n；seqqueueq；/*假设采用顺序队列，定义顺序队列类型变量q*/n=g-n；init_seqqueue（q）；/*队列初始化*/printf(“访问出发点%d”,v)；/*访问出发点，假设为输出顶点序号*/visidv=1；/*置访问标志为1，表示此点已访问过*/en_sqqueue（q，v）；/*顶点v入队*/while(!empty_Seqqueue(q)/*队列空否？*/de_sqqueue（q，v）；/*队列非空时，出队*/for（j=l；jadgesvj=l！visidj）printf(“访问顶点%d”，j)；visidj=1；/*置顶点j被访问标志*/en_seqqueue(q，j)；/*顶点j入队*/,voidBFSL（graph*g，intv）/*采用邻接表存储结构，BFS遍历*/seqqueueq；/*假设采用顺序队列,定义顺序队列类型变量q*/pointerp；init_seqqueue（q）；/*队列初始化*/printf（“访问出发点%d”,v）；/*访问出发点，假设为输出顶点序号*/visidv=1；/*置访问标志为1，表示此点已访问过*/en_seqqueue（q，v）；/*顶点v入队*/while（！empty_seqqueue（q）de_seqqueue（q，v）；p=g-adlistvfirst；While（p!=NULL）if（!visidp-vertex）printf(%d”，p-vertex)；visidp-vertex=1；en_seqqueue(q，p-vertex)；p=p-next；,算法分析,如果使用邻接表表示图，则循环的总时间代价为d0+d1+dn-1=O(e)，其中的di是顶点i的度。如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的n个元素，总的时间代价为O(n2)。,非连通图的遍历,非连通图的遍历必须多次调用深度优先搜索或广度优先搜索算法，以DFS为例：,TRAVER()/*遍历用邻接矩阵表示的非连通图*/inti;for(i=0;i0for(i=1;iadlistv.first；,while（p!NULL）g-adlistp-vertex.id-；if（q-adlistp-vertex.id=0）push_Ikstack（s，p-vertex）；