第十二章 图1.ppt

第十二章图,12.1何谓图形结构,欧拉将7桥问题所区别的4个区域，定义成图形中的4个顶点(Vertices)，把7座桥定义成图形中的7个边(Edges)，最后他发现如果任一个区域(顶点)上所连结的桥数(边数)为偶数，才有可能从任一座桥(顶点)出发，经过每一座桥(边)而回到出发的区域(顶点)，我们称这种走法为“欧拉走法(EulerianWalk)”。欧拉的7桥问题图形如右：由欧拉的发现中，我们可以了解到7桥问题是没有解的，因为在7桥问题中，每一个顶点皆是奇数个边。从7桥问题中，我们已经对图形有了基本的认识了。图的定义为“在图G中包含了两个集合，一个是由顶点(Vertices或nodes)所构成的有限的非空集合，另一个是由边(Edges或Arcs)所构成的有限非空集合。”我们可以G(V,E)来表示。,12.1何谓图形结构,图G（Graph）是由两个集合V(G)和E(G)组成的二元组，记作G=(V,E)。其中V(G)是顶点的非空有限集，E(G)是边的有限集，边是顶点的无序对或有序对。,顶点的集合V=A，B，C，D，E，F边的集合E=（A，B），（A，C），（B，D），（C，D），（D，F），（C，F），（D，E），（E，F）,12.1何谓图形结构,在图G中，若边的集合E(G)是有向边的有限集合，则称该图为有向图（Digraph），这里的有向边又称为弧(Arc)，弧是顶点的有序对，为便于区别，用尖括号括起来，记作，其中x被称为弧尾（tail）或起始点，y被称为弧头（head）或终端点。,上图表示的是一个有向图，在该图中，顶点的集合V=A，B，C，D，E，F边的集合E=，（F，C），。,12.1.1无向图,无向图(UndirectedGraph)是指在图中任一顶点上的边都是没有方向性的。例如右图就是一个无向图，因为任意两个顶点间的边都没有方向性，如顶点1和顶点2之间的边表示可从顶点1到顶点2，也可以从顶点2到顶点1。,12.1.2有向图,有向图(DirectedGraph)是指在图中任一顶点上的边都是有方向性的。例如右图就是一个有向图，因为任意两个顶点间的边都是有方向性，如顶点1和顶点2之间的边表示可从顶点1到顶点2，但是不可以从顶点2到顶点1。对有向图和无向图，我们还必须加上一些限制：图中不允许有自身循环两顶点间的边不可以重复,12.1.3完全图,完全图CompleteGraph)是指在无向图中任意两顶点上的都存在一个边。例如右图就是一个完全图，因为任意两个顶点间的都存在一个边。很显然具有n个顶点的完全图的边数为n(n-1)/2。,顶点的度,关联：若边（x，y）是一条无向边，则称边（x，y）关联于顶点x和y，或称边（x，y）与顶点x和y相关联。若弧是一条有向边，则称弧与顶点s和t相关联。顶点的度（Degree）：顶点v的度是和x相关联的边的数目，记为D(v)。若G是有向图，则以顶点v为终端点的弧的数目称为v的入度（InDegree，内分支度），记为ID(v)；以顶点v为起始点的弧的数目称为v的出度（OutDegree，外分支度），记为OD(v)，根据定义有：D(V)=ID(v)+OD(v)。,12.1.4子图,子图(Sub-Graph)是指由图G中取出的部分集合，如右图为图G。若G=(V,E)是一个图，V是V的子集，E是E的子集，且E中所有边相关联的顶点均在V，中，则G=(V,E)也是一个图，称其为图G的一个子图。,12.1.5路径,路径是指在图中从顶点A到达顶点B，所经过上的所有的边。例如下图从顶点1到顶点5的路径为,，而路径的长度为经过的边数，在这个例子中，路径的长度为3。,12.1.6简单路径,所谓的简单路径(SimplePath)是指在图中，除了起点和终点可以重复(不重复亦可)外，其余的顶点皆不相同的路径，如上图的,，为简单路径，而,不是简单路径，因为在这条路径中顶点1和顶点2重复经过。,12.1.7回路,回路(Cycle)是指在图中，起点和终点相同的简单路径，如右图中，、就是一条回路、而、，也是一条回路。,12.1.8连通顶点,所谓的连通顶点(ConnectedVertices)是指在无向图中，顶点A到顶点B间存在一条路径，则称顶点A和顶点B为连通顶点。,12.1.9连通图,如果在无向图中，任意两个顶点间皆连通，则称为连通图(ConnectedGraph)。即任意两个顶点皆存在有一条路径可到达。,12.1.10连通单元,所谓的连通单元(ConnectedComponent)是将无向图分为多个分离的子图之后，原图的连通顶点仍在同一个子图中，如下图所示。,12.1.11强连通顶点,所谓的强连通顶点(StronglyConnectedVertices)是指在有向图中，顶点A到顶点B间存在一条路径，而顶点B到顶点A间也存在一条路径，则称顶点A和顶点B为强连通顶点。,12.1.12强连通图,如果在有向图中，任意两个顶点间皆存在一条路径可到对方，则称为强连通图(StronglyConnectedGraph)。,12.1.13强连通单元,所谓的强连通单元(ConnectedComponent)是将有向图，分为多个分离的子图之后，原图的连通顶点仍在同一个子图中。除了以上的定义外，对于特殊的图结构。如树状结构的图，我们定义为：自由树是指一个相连非循环的无向图。如果一棵自由树，有一个特定的顶点作为树根，则称为有根树(RootedTree)。,生成树：一个具有n个顶点的连通图的生成树是一个连通单元，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。,生成树,无向图生成树生成树,加权图,加权图：若无向图的每条边都有一个权值，则称其为加权无向图。同理，若有向图的每条弧都有一个权值，则称其为加权有向图。这里的权值往往代表某种具体的意义，如距离、代价等。,（a）加权无向图（b）加权有向图,12.2图的表示法,12.2.1邻接数组表示法邻接数组表示法(AdjacentMatrix)是以一个n*n的数组来表示一个具有n个顶点的图。以数组的内容值来表示顶点间的边是否存在(以1表示存在边，以0表示不存在边)。假定图G=(V,E)有n个顶点，则可用如下n阶方阵来表示G：,12.2.1邻接数组表示法,假定图G=(V,E)有n（n=1）个顶点，则可用如下n阶方阵来表示G的邻接数组：,12.2.1邻接数组表示法,邻接矩阵的如下性质：（1）由于不考虑顶点到自身的边或弧，邻接矩阵的对角线元素为零。（2）无向图的邻接矩阵为对称矩阵，故可用压缩存储的方式只存储其上（下）三角部分即可，这一点在第2章已有介绍，这里不再赘述。（3）用邻接矩阵表示一个有n个顶点的有向图时，所需空间复杂度为O（n2），访问该矩阵的时间复杂度也为O（n2）。,/*以邻接数组建立图形*/voidCreate_M_Graph(intVertice1,intVertice2)GraphVertice1Vertice2=1;/*将数组内容设为1*/*主程序*/voidmain()for(i=0;i=Max|Destination=Max)printf(Error:Outofrange!n);else/*调用建立邻接数组*/Create_M_Graph(Source,Destination);printf(#Graph#n);Print_M_Graph();/*调用输出邻接数组数据*/,12.2.2邻接列表表示法,邻接列表法(AdjacencyList)是以链表来记录各顶点的邻接顶点：用一个一维数组存储图中所有顶点，在每个顶点对应的数据元素后挂一个单链表，该链表的接点存储与其相连顶点的信息。节点结构如下：,12.2.2邻接列表表示法,在C语言中，邻接列表的结构声明如下：structNodeintVertex;structNode*Next;typedefstructNode*Graph;structNodeHeadVerticeNum;,12.2.2邻接列表表示法,有向图的邻接列表,12.2.2邻接列表表示法,无向图的邻接列表,/*建立邻接顶点至邻接列表内*/voidCreate_L_Graph(intVertex1,intVertex2)GraphPointer;/*节点声明*/GraphNew;/*新顶点声明*/New=(Graph)malloc(sizeof(structNode);/*配置内存*/if(New!=NULL)/*配置成功*/New-Vertex=Vertex2;/*邻近顶点*/New-Next=NULL;/*下一个邻接顶点指针*/*Pointer指针设为顶点数组之首节点*/Pointer=/*串连在链接尾端*/,12.2.2邻接列表表示法,假定无向图有n个顶点和e条边，则采用邻接表存储需要n个头结点和2e个表结点。显然，当eVertex1=Source;/*邻近顶点*/Create_ML_Graph(Source,New);if(Choose=1)Create_ML_Graph(Destination,New);for(i=0;iVertex1=Vertex1)/*往Edge1的下一个节点*/Pointer=Pointer-Edge1;else/*往Edge2的下一个节点*/Pointer=Pointer-Edge2;if(Previous=NULL)/*串连在Head之后*/HeadVertex1.Next=New;elseif(Previous-Vertex1=Vertex1)Previous-Edge1=New;/*串连在Edge1之后*/elsePrevious-Edge2=New;/*串连在Edge2之后*/,12.2.4加权边的图,有时候，我们会在图的边上加上一些数字（权值），来代表某种具体的意义，如距离、代价等，我们称之为“加权图(WeightedEdgesGraph)”。如下图就是一个加权图：,可以将该加权图表示为G(V,E)，其中：V(G)=0，1，2，3E(G)=(0,1)6,(0,2)9,(0,3)3,(1,2)7,(2,3)2如果用邻接数组来表示加权图，则数组的元素值必须做出调整：元素值代表对应边的权值，0仍然表示不存在边。如果用邻接列表或多重邻接列表来表示加权图，则列表节点必须添加一个记录权值的字段。,12.3图的查找,从图中某个顶点出发遍历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。,12.3.1深度优先法,从图中某个顶点V0出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。,12.3.1深度优先法,深度优先搜索（DepthFirstSearch）算法的步骤为：（1）首先访问图中的某个顶点v。（2）找出与顶点v邻接的第一个未被访问的w，对该顶点进行访问。再以顶点w为新顶点，重复本步骤，直到当前顶点没有未被访问的邻接点为止。（3）当某个顶点的所有邻接顶点都被访问过时，就从这个顶点依次返回到被访问过的顶点，直到某顶点的邻接顶点中有未被访问的顶点，从中找到一个未被访问的顶点，执行步骤（2）。,voidmain()inti;intNode202=1,2,2,1,1,3,3,1,2,4,;for(i=0;i);DFS(1);printf(END);,/*深度优先搜索法*/voidDFS(intVertex)GraphPointer;/*节点声明*/VisitedVertex=1;/*已查找*/printf(%d=,Vertex);Pointer=HeadVertex.Next;while(Pointer!=NULL)if(VisitedPointer-Vertex=0)DFS(Pointer-Vertex);/*递归调用*/Pointer=Pointer-Next;/*下一个邻接点*/,12.3.2广度优先法,从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。,算法实现：通常是使用队列来存储邻接顶点，每查找一个邻接顶点便把其所有的邻接顶点存入队列中，直到队列空了才结束广度优先搜索。,/*广度优先搜索法*/voidBFS(intVertex)GraphPointer;/*节点声明*/Enqueue(Vertex);/*存入队列中*/VisitedVertex=1;/*已查找*/printf(%d=,Vertex);while(Front!=Rear)/*队列为空时，结束循环*/Vertex=Dequeue();Pointer=HeadVertex.Next;while(Pointer!=NULL)/*读入邻接列表所有顶点*/if(VisitedPointer-Vertex=0)Enqueue(Pointer-Vertex);/*存入队列中*/VisitedPointer-Vertex=1;/*已查找过的顶点*/printf(%d=,Pointer-Vertex);Pointer=Pointer-Next;/*下一个邻接点*/,12.3.3连通组件,连通图的判断，通常只要建立图之后，只要从第一个顶点做深度优先搜索或广度优先搜索，之后看看是不是所有的顶点都查找过，如果所有的顶点都查找过，则表示这个图是连通的图，否则表示这个图不是连通的图。连通组件的判断，也只需要重复的对未查找过的顶点做深度优先搜索或广度优先搜索，输出边，即可输出图的连通组件。,对非连通图，从某一顶点开始深度优先遍历其所在的连通分量，然后检测图中所有顶点是否已经被全部访问过，如果是，则说明该图为连通图，遍历结束；如果还有顶点没有被访问，则选定一个未被访问的顶点作为起始点，并对其所在的连通分量采用深度优先算法进行遍历，如此下去，直到所有顶点均被访问为止。,12.4生成树问题,12.4.1生成树在图中，如果有N个顶点，则至少要有N-1个边才能将N个顶点给相连起来，形成连通图，这种包含着N1个边的连通图，我们称之为生成树(SpanningTree)。一个连通图可以有多棵不同的生成树，这是因为遍历图时选择的起点不同，采用的策略不同，访问顺序不同，因而遍历所经过的边也不同，这样就产生了不同的生成树。,12.4.2最小生成树,在一个加权边图的所有生成树中，加权值总和最小的生成树，我们称之为“最小生成树(MinimalSpanningTree)”。例如：我们要建设局域网络，而其局域网络上有5栋大楼，为了能运用网络来连接各栋大楼，所以我们必须在大楼与大楼间使用网络线，经过初步的测量之后，我们得到下列这张图(边上的加权值为距离)：如果能找出这张图的最小生成树，即可以用最少的网络线串连5栋大楼，完成局域网络的建设。,12.4.2最小生成树,算法一：（克鲁斯卡尔算法）算法二：（普里姆算法）,12.4.3Kruskal算法,考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。具体做法:依次找出加权值最低的边来建最小生成树，而且规定：每次添加的边不能造成生成树有回路，直到找到N1个边为止。,12.4.3Kruskal算法,程序构思：先将所有的邻接边依加权值递增用链表链接起来。另声明一个一维数组Visited，表示现在生成树集合中的顶点，用于判断是否产生回路。用1表示生成树的顶点，0表示非生成树的顶点，如果新加入的邻接边中两个顶点皆在生成树集合中，表示会产生回路。利用Kruskal算法之前建立的链表来加入生成树的邻接边，直到产生N1个边为止。最后将结果输出。,voidmain()EdgeHead;/*节点声明*/inti;Head=NULL;for(i=0;iVertex1=Edges00;/*定义节点加权值*/Head-Next=NULL;for(i=1;iVertex1=Edgesi0;/*定义节点加权值*/New-Next=NULL;Head=Insert_Edge(Head,New);/*则插入新节点*/returnHead;,/*递增插入邻接边至链表内*/EdgeInsert_Edge(EdgeHead,EdgeNew)EdgePointer;/*节点声明*/Pointer=Head;/*Pointer指针设为首节点*/while(1)if(New-WeightWeight)/*新的加权值比首节点小*/New-Next=Head;/*插入在首节点之前*/Head=New;break;/*插入在链表中间或尾端*/if(New-Weight=Pointer-Weight)if(Pointer-Next=NULL)|(New-WeightNext-Weight)New-Next=Pointer-Next;Pointer-Next=New;break;Pointer=Pointer-Next;/*往下一个节点*/returnHead;,/*Kruskal算法*/voidKruskal(EdgeHead)Pointer=Head;/*当边的数目为顶点的数目减1时，结束循环*/while(EdgeNum!=(VertexNum-1)/*有一顶点不在生成树中时*/if(VisitedPointer-Vertex1=0|VisitedPointer-Vertex2=0)printf(=%d,%d,Pointer-Vertex1,Pointer-Vertex2);printf(%d),Pointer-Weight);Weight+=Pointer-Weight;EdgeNum+;/*边数加1*/VisitedPointer-Vertex1=1;/*设为已查找*/VisitedPointer-Vertex2=1;/*设为已查找*/Pointer=Pointer-Next;/*往下一个节点*/if(Pointer=NULL)/*已无边时*/printf(NoSpanningTreen);break;printf(nTotalweight=%dn,Weight);/*输出加权值总和*/,12.4.4Prims算法,取图中任意一个顶点v作为生成树的根，之后往生成树上添加新的顶点w。在添加的顶点w和已经在生成树上的顶点v之间必定存在一条边，并且该边的权值在所有连通顶点v和w之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有n-1个顶点为止。,一般情况下所添加的顶点应满足下列条件:在生成树的构造过程中，图中n个顶点分属两个集合：已落在生成树上的顶点集U和尚未落在生成树上的顶点集V，则应在所有连通U中顶点和V中顶点的边中选取权值最小的边（最小邻接边）。,12.4.4Prims算法,程序构思：先将所有的邻接边用链表链接起来。另声明一个一维数组Tree，表示现在生成树集合中的顶点，用于判断是否产生回路。用1表示生成树的顶点，0表示非生成树的顶点，如果新加入的邻接边中两个顶点皆在生成树集合中，表示会产生回路。利用Prims算法将之前建立的链表来加入生成树的邻接边，直到产生N1个边为止。最后将结果输出。,voidmain()EdgeHead;/*节点声明*/inti;for(i=1;iNext;if(minPointer-Weight)MinEdge=Pointer;/*找出加权值最小的邻接边*/min=MinEdge-Weight;while(Pointer!=NULL)if(VisitedPointer-Vertex1=1,VisitedMinEdge-Vertex1=1;/*将顶点1设为存在生成树集合中*/VisitedMinEdge-Vertex2=1;/*将顶点2设为存在生成树集合中*/EdgeNum+;/*生成树的边数加1*/Weight+=