图论问题和算法-4

图论问题和算法秦高德2014.11图V1V4V2V3V5V4V3V2V1结点之间的关系：多对多，任两个结点之间都可能有关系存在.定义和术语v1图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)其中：V(G)是顶点的非空有限集E(G)是边的有限集合，边是顶点的无序对或有序对有向图——有向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为v,w，v,w是顶点，v为弧尾，w为弧头无向图——无向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集E(G)是边的有限集合，边是顶点的无序对，记为(v,w)或(w,v)，并且(v,w)=(w,v)v3v2v1v1v2v4v3定义和术语图G1中：V(G1)={V1,V2,V3}E(G1)={V1,V2,V2,V1,V2,V3}图G2中：V(G2)={V1,V2,V3,V4}E(G1)={(V1,V2),(V1,V3),(V1,V4),(V2,V3),(V2,V4),(V3,V4)}v3v2v1v1v2v4v3定义和术语对于有n个顶点的无向图，边或弧e的取值范围是0到n(n-1)/2，即0～𝑪𝒏𝟐对于有n个顶点有向图，e的取值范围是0到n(n-1)即0～𝑷𝒏𝟐，例213213完全有向图完全无向图定义和术语有时图的边或弧具有与它相关的数，这种与图的边或弧相关的数叫做权。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网(Network)。子图——如果图G(V,E)和图G‘(V’,E‘),满足：V’VE’E则称G‘为G的子图356例245136图与子图683定义和术语无向图：顶点v的度(Dgeree)是和v相关联的边的数目，记为TD(V)。有向图：以顶点v为头的弧的数目称为v的入度，记为ID(v)以v为尾的弧的数目称为v的出度，记为OD(v)顶点v的度TD(v)=ID(v)+OD(v)157324G26245136G1顶点5的度：3顶点2的度：4顶点2入度：1出度：3顶点4入度：1出度：0定义和术语无向图G(V,{E})中从顶点v到顶点v‘的路径(Path)是一个顶点序列（v=vi,0,vi,1,…,vi,m=v’），其中(vij-1,vi,j)∈E,1≤j≤m。i=1,2,…,k，表示v到v’间有k条路径。如果G是有向图，则路径也是有向的，顶点序列应满足vi,j-1,vi,j∈E,1≤j≤m。路径的长度是路径上的边的数目。第一个顶点和最后一个顶点相同的路径称为回路或环(Cycle)。序列中顶点不重复的出现的路径称为简单路径。除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路，称为简单回路或简单环。例157324G26例245136G1路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，3路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，1定义和术语在无向图G中，如果从顶点v到顶点v'有路径，则称v和v'是连通的。如果对于图中任意两个顶点vi,vj和都是连通的，则称G是连通图(ConnectedGraph)所谓连通分量(ConnectedComponent)是指无向图中的极大连通子图。CABDEFBDEFCA定义和术语有向图G中，如果对于每一对vi,vj∈V，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。v3v2v1v3v2v1定义和术语连通图例245136强连通图356例非连通图连通分量例245136图的遍历图的遍历（TraversingGraph）:从图中某一个顶点出发，访问图中的其余顶点，且使每个顶点仅被访问一次。方法：深度优先搜索DFS广度优先搜索BFS图的遍历深度优先搜索：V1-V2-V4-V8-V5-V6-v3-v7广度优先搜索V1-V2-V3-V4-v5-v6-v7-v8v2v4v1v5v3v6v7v8图的遍历:深度优先搜索深度优先搜索（DepthFirstSearch）1从任一个顶点v出发，访问该顶点；2然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；3此时若图中尚有顶点未被访问（不与v连通的点），则另选下中下一个未被访问的顶点作起始点，访问该顶点，继续过程2。深度优先遍历算法递归算法开始访问V0,置标志求V0邻接点有邻接点w求下一邻接点wV0W访问过结束NYNYDFS开始标志数组初始化Vi=0Vi访问过DFSVi=Vi+1Vi==Vexnums结束NNYY图的遍历:深度优先搜索intvisited[MAXNODE]//访问标志数组voidDFSTraverse(GraphG){//初始访问数组置未访问标志for(v=0；vG.vernum；v++)visited[v]=0；for(v=0；vG.vernum；v++)if(!visited[v])DFS(G,v)；//对未访问过的顶点调用DFS}//从第v个顶点出发递归地深度优先遍历图GvoidDFS(GraphG,intv){visited[v]=1；visit[v]；//访问v顶点（输出v）for(w=GraphFirstAdj(G,v)；w；w=GraphNextAdj(G,v,w))if(!visited[w])DFS(G,w)；}图的遍历:广度优先搜索广度优先搜索1从图中某顶点v出发，在访问v之后，2依次访问v的各个未曾被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已经被访问的顶点的邻接点都被访问到；3若图中尚有顶点未曾被访问，则另选图中一个未曾被访问的顶点作起使点，访问该顶点，继续过程2广度优先遍历算法开始标志数组初始化Vi=0Vi访问过BFSVi=Vi+1Vi==Vexnums结束NNYY图的遍历:广度优先搜索voidBFSTraverse(GraphG，intv){for(v=0；vG.vernum；v++)QueueInit(Q)；for(v=0；vG.vernum；v++)if(!visited[v]){QueueIn(Q,v)；while(!QueueEmpty(Q)){QueueOut(Q,u)；visited[u]=1；visit(u)；for(w=GraphFirstAdj(G,u)；w；w=GraphNextAdj(G,u,w))if(!visited[w])QueueIn(Q,w)；}//while}//if}9.3图的存储结构对于网，可以用aij表示权。若vi和vj不邻接（或没有vi邻接到vj），则可以用无限大∞表示权。，其它0E(G)v,v或)v,(v若1,],[jijijiA邻接矩阵——表示顶点间相联关系的矩阵定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵，其它0E(G)v,v或)v,(v若,],[jijiijjiA图的存储结构：数组表示0111101111011110v3v2v4v1v3v2v1000101010v1v3v2v432457754231无向图的数组表示(1)无权图的邻接矩阵无向无权图G=(V，E)有n(n≧1)个顶点，其邻接矩阵是n阶对称方阵，如图7-5所示。其元素的定义如下：1若(vi,vj)E，即vi,vj邻接0若(vi,vj)E，即vi,vj不邻接A[i][j]=(a)无向图abcd图7-5无向无权图的数组存储(b)顶点矩阵vexsabcd0111101111011110(c)邻接矩阵(2)带权图的邻接矩阵无向带权图G=(V，E)的邻接矩阵如图7-6所示。其元素的定义如下：(a)带权无向图(b)顶点矩阵图7-6无向带权图的数组存储(c)邻接矩阵354126abcde3vexsabcde∞62∞∞6∞34323∞1∞∞43∞5∞3∞5∞Wij若(vi,vj)E，即vi,vj邻接，权值为wij∞若(vi,vj)E，即vi,vj不邻接时A[i][j]=(3)无向图邻接矩阵的特性◆邻接矩阵是对称方阵；◆对于顶点vi，其度数是第i行的非0元素的个数；◆无向图的边数是上(或下)三角形矩阵中非0元素个数。2有向图的数组表示(1)无权图的邻接矩阵若有向无权图G=(V，E)有n(n≧1)个顶点，则其邻接矩阵是n阶对称方阵，如图7-7所示。元素定义如下：1若vi,vjE，从vi到vj有弧A[i][j]=0若vi,vjE从vi到vj没有弧(a)有向图acbde图7-7有向无权图的数组存储(b)顶点矩阵vexsabcde(c)邻接矩阵0110100000000111100000010(2)带权图的邻接矩阵有向带权图G=(V，E)的邻接矩阵如图7-8所示。其元素的定义如下：wij若vi,vjE，即vi,vj邻接，权值为wij∞若vi,vjE，即vi,vj不邻接时A[i][j]=图7-8带权有向图的数组存储(b)顶点矩阵vexsabcde(c)邻接矩阵∞62∞∞∞∞∞∞3∞3∞1∞∞4∞∞5∞∞∞∞∞(a)带权有向图354126abcde3⑶有向图邻接矩阵的特性◆对于顶点vi，第i行的非0元素的个数是其出度OD(vi)；第i列的非0元素的个数是其入度ID(vi)。◆邻接矩阵中非0元素的个数就是图的弧的数目。图的存储结构：数组表示对于无向图：矩阵一定是一个对称阵行（或列）非零个数，表示顶点的度对于有向图：矩阵不一定是一个对称阵行非零个数，表示出度列非零个数，表示入度图的存贮结构__数组表示#defineMAXNODE…//图中顶点的最大个数typedefstruct{vertypevertex;//顶点信息…;//和顶点相关的其它信息}VerNode;typedefstruct{intadj;//两顶点之间是否存在关系…；//和弧（或边）相关的信息}Arc;typedefstruct{VerNodevexs[MAXNODE];Arcarcs[MAXNODE][MAXNODE];}Graph;//邻接矩阵typedefintAdjMatrix[MAXNODE][MAXNODE];图的存储结构：邻接表基本思想：对图的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。每一个单链表设一个表头结点。第i个单链表表示依附于顶点Vi的边(对有向图是以顶点Vi为头或尾的弧)。图的存储结构：邻接表在这种表示法中，对于图中每个顶点建立一个链表类似于树的孩子表示法，如果能把图中任一个顶点的所有邻接点都表示出来，也就可以表示图。无向图的第i个链表将图中与顶点vi相邻接的所有顶点链接起来，也就是链表中的表头结点到链表中的每个结点表示了与表头结点vi相关的边有向图的第i个链表，链接了以顶点vi为尾（射出）的所有头（射入）顶点，也就是链表中的表头结点到链表中的每个结点表示了图中关联到表头结点vi的所有边在图的邻接链表表示中，所有顶点结点用一个向量以顺序结构形式存储，可以随机访问任意顶点的链表，该向量称为表头向量，向量的下标指示顶点的序号。用邻接链表存储图时，对无向图，其邻接链表是唯一的，如图7-10所示；对有向图，其邻接链表有两种形式，如图7-11所示。图7-10无向图及其邻接链表v1v2v3v4v501234MAX_VEX-1v1v2v3v4┇┇v5213⋀02⋀0314⋀204⋀23⋀(a)有向图v1v2v3v4v513⋀01