数据结构第八章图

合肥工业大学计算机与信息学院1数据结构（第八章图）DataStructures胡学钢张晶计算机与信息学院2009年2月合肥工业大学计算机与信息学院2第八章图(Graph)第八章图（Graph)8.1基本概念和运算8.2图的存储8.3图的遍历8.4最小生成树8.5有向无环图的应用8.6最短路径合肥工业大学计算机与信息学院38.1基本概念和运算图——由顶点集V和连接顶点的弧集E所组成的结构，记作G=(V,E)。其中弧的形式为Vi,Vj，表示从顶点Vi到Vj之间有一条弧，图形表示为：Vi—Vj——有向图例：如右图中的G1就是一个有向图：其中：顶点集合V={1，2，3，4}弧集E={1,2,1,3,2,4,3,4,4,1}2134图G1有向图示例合肥工业大学计算机与信息学院48.1基本概念和运算如果顶点间的关系是相互的，即弧的两端没有方向，则图为无向图。其中的弧称为边。边的形式为(Vi,Vj)，图形表示为：Vi——Vj例：如右图中的G2就是一个无向图：其中：顶点集合V={1，2，3，4}边集E={（1,2）,（1,3）,（1,4）（2,4）,（3,4）}2134图G2无向图示例合肥工业大学计算机与信息学院58.1基本概念和运算若G中每条边（弧）对应一个数值——表示关系的程度，则称图G为网络。例：图G3就是一个网络对图G=(V,E)，若存在G1=(V1，E1)，满足V1≤V，E1≤E。则G1是G的子图。例如：右图G4就是G2的子图。213465837图G3网络示例2134图G4子图示例2134图G2无向图示例合肥工业大学计算机与信息学院68.1基本概念和运算顶点间关系：如果Vi,Vj∈E则称——Vi，Vj相邻接，Vi邻接到Vj，Vj邻接自Vi。例如，右图中，V1邻接到V2，V4邻接自V3若(Vi,Vj)∈E——则称Vi，Vj相邻接顶点的度——顶点的邻接点的数目。有向图中：入度，出度。度＝入度＋出度。2134图G1有向图示例合肥工业大学计算机与信息学院78.1基本概念和运算路径——若顶点序列Vi1，Vi2，…，Vik，满足Vil，Vi(l+1)∈E或者(Vil，Vi(l+1))∈E）（l=1,2,…,k-1），则该顶点序列Vi1，Vi2，…，Vik构成一条路径。例:图G1中，1,2,4,1,3,4是一条路径简单路径——中间经过的顶点不重复的路径。例:图G1中，(1,2,4)(1,3,4)(1,3,4,1)都是简单路径。回路——首尾相同的路径。例如，(1,3,4,1)简单回路——简单路径+回路2134图G1有向图示例合肥工业大学计算机与信息学院88.1基本概念和运算若无向图中任意两点间都存在路径——则称为连通图。否则，称为不连通图（非连通图）。非连通图包含若干连通分量——极大连通子图。若有向图中的任意两点间可以互相到达——则称为强连通图。12534连通图示例6712534非连通图示例—三个连通分量6712534强连通图示例合肥工业大学计算机与信息学院98.1基本概念和运算若无向图中任意两点间都有一条边——则称为无向完全图。（共有n(n-1)/2条边）若有向图中每个顶点到其余各点均有一条弧——则称为有向完全图。（共有n(n-1)条边）125345阶无向完全图21344阶有向图示例合肥工业大学计算机与信息学院108.1基本概念和运算若无向图满足：连通并且无回路——则称为树。树的定义有如下几个等价的描述：有最少边数的连通图。有n-1条边的连通图。连通的无环图。有向树——如果在有向图中，有一个顶点的入度为0，其余顶点的入度为1，则称此图为有向树。并称其中入度为0的顶点为有向根。右下图就是一个有向树，其中顶点1就是有向根。6712534树的示例6712534有向树示例合肥工业大学计算机与信息学院118.1基本概念和运算图的运算：基本运算：初始化图插入顶点插入边（弧）修改权值删除顶点删除边（弧）求指定顶点的邻接点常用运算：遍历合肥工业大学计算机与信息学院128.1基本概念和运算邻接点的求解方法：具体实现依赖于图的存储结构，可以考虑用两个运算来实现求解：intfirstadj(G,v);返回顶点v的第一个邻接点号。若不存在时，返回0（或定义为-1）。intnextadj(G,v,w);返回顶点v的邻接点中处于邻接点w之后的邻接点号。若不存在时，返回0（或定义为-1）。合肥工业大学计算机与信息学院138.2图的存储图的存储——图结构在计算机中的存储形式1.邻接矩阵（1）不带权值假设图中有n个顶点。则采用n×n的矩阵A来表示，1i，j∈E其中Aij＝0否则例：13240110000100011000行的方向：发出的弧列的方向：进入的弧对应关系合肥工业大学计算机与信息学院148.2图的存储（2）网络的表示方法wiji，j∈EAij＝0或∞否则例：∞4354∞∞23∞∞6526∞12430111100110011110无向图的邻接矩阵对称142363524合肥工业大学计算机与信息学院158.2图的存储2.邻接表表示法——将邻接点构成链表例：12341243datafirstadj234^14^14^123^对应关系合肥工业大学计算机与信息学院168.2图的存储逆邻接链表——将“邻接自”的顶点连成链表1234datafirstadj4^1^1^3^43213^212344^4^1^2datafirstadj对应关系代表弧4,1合肥工业大学计算机与信息学院178.3图的遍历图的遍历——访问图中所有顶点一次且仅且一次。深度优先搜索遍历图的两种遍历算法广度优先搜索遍历8.3.1深度优先搜索遍历（DepthFirstSearch)这一问题求解包括几个部分。1.基本算法从顶点v0出发深度优先搜索遍历图G的dfs(v0)描述如下：(1)访问v0；(2)依次从v0的未被访问过的邻接点出发深度遍历。合肥工业大学计算机与信息学院18dfs(8)dfs(9)dfs(4)dfs(3)8.3.1深度优先搜索遍历下面以下图为例来讨论dfs算法的执行过程：调用dfs(1)此箭头表示是从遍历运算dfs(1)中调用dfs(2)，即从顶点1直接转到2此虚箭头表示是在dfs(3)执行完毕后返回到遍历运算dfs(2)中，即从顶点3返回到267125348109dfs(1)dfs(2)dfs(5)dfs(6)dfs(7)dfs(10)在访问顶点3后，由于顶点3的邻接点已全被访问，故dfs（3）执行到此结束，应返回到调用层，即返回到dfs(2)dfs(1)包含如下两部分操作：（1）访问顶点1；（2）依次执行dfs(2)和dfs(8)合肥工业大学计算机与信息学院198.3.1深度优先搜索遍历将dfs（1）执行过程中所搜索的边连接起来（有标注的边），得到一棵生成树----dfs生成树。6712534810967125348109原图及其搜索示意图dfs(1)生成树合肥工业大学计算机与信息学院208.3.1深度优先搜索遍历下面讨论dfs算法的设计。为此，先回顾一下dfs(v0)的描述：(1)访问v0；(2)依次从v0的未被访问过的邻接点出发深度遍历。分析：由算法描述可知：①访问顶点v0的基本操作：可用visite(v0)简单表示。②设置访问标志数组visited[]，并约定：某顶点vi未被访问时，visited[i]==FALSE（初值）vi被访问过后，visited[i]==TRUE（初值）③求邻接点可以采用两个函数：firstadj(G,v)：返回v的第一个邻接点（号），或0（不存在时）。nextadj(G,v,w);返回v的第邻接点中处于邻接点w之后的邻接点号,或0（不存在时）访问v0时，visited[i]=TRUE;合肥工业大学计算机与信息学院21YN8.3.1深度优先搜索遍历由讨论可得到dfs算法的流程图如下：由此得深度遍历基本算法dfs(v0)如下:voiddfs(intv0){visite(v0);visited[v0]=TRUE;w=firstadj(G,v0);while(w!=0){if(!visited[w])dfs(w);w=nextadj(G,v0,w);}}Nvisite(v0);visited[v0]=TRUE;W==0?W被访问过？Ndfs(w);w=nextadj(G,v,w);w=firstadj(G,v)：合肥工业大学计算机与信息学院228.3.1深度优先搜索遍历问题：（1）dfs算法是否适用于有向图？（2）如何设置标志数组visited[]的初值？能否在dfs算法中设置？（3）从某顶点出发是否能保证访问到所有顶点？或者说：选择一个起点调用一次dfs算法，能否实现对整个图的遍历？2.遍历整个图的算法dfs算法在应用于非连通图，或者是某些有向图时，某一次调用就不能保证访问到所有顶点。如下图所示。61253467125348109合肥工业大学计算机与信息学院238.3.1深度优先搜索遍历为此，需要重新选择起点来调用dfs算法。如何选择新的起点？起点应满足什么条件？将对访问标志数组的赋初值运算，以及选择起点的控制合在一起，构成对整个图的遍历算法如下：voidtravel_dfs(graphG){for(i=1;i=n;i++)visited[i]=FALSE;for(i=1;i=n;i++)if(!visited[i])dfs(i);}合肥工业大学计算机与信息学院248.3.1深度优先搜索遍历3.深度遍历算法的应用问题：（1）如何设计算法以判断给定的无向图是否是连通的？（2）如何设计算法以求解给定的无向图中的边数？（3）设计算法以判断给定的无向图是树。（4）设计算法以判断给定的有向图是以v0为根的有向树。（5）设计算法以判断图中的一个节点是否为关节点。合肥工业大学计算机与信息学院258.3.1深度优先搜索遍历例1设计算法以求解无向图G的连通分量的个数。分析：对无向图G来说，选择某一顶点v执行dfs(v)，可访问到所在连通分量中的所有顶点因此，选择起点的次数就是图G的连通分量数，这可通过修改遍历整个图的算法dfs_travel来实现：每调用一次dfs算法计数一次。另外，考虑到要求求解连通分量数，因而可以将算法设计为整型函数。具体算法如下：合肥工业大学计算机与信息学院268.3.1深度优先搜索遍历intnumofGC(graphG){inti;intk=0;//k用于连通分量的计数for(i=1;i=n;i++)visited[i]=FALSE;for(i=1;i=n;i++)if(visited[i]==FALSE){k++;dfs(G,i);}//用k来累计连通分量个数returnk;}遍历整个图的算法dfs_travel中的原来的部分合肥工业大学计算机与信息学院278.3.1深度优先搜索遍历例2设计算法求出无向图G的边数。算法如下：voiddfs(graphG,intv){intw;visited[v]=TRUE;//设置访问标志（访问结点的其它操作被省去）w=firstadj(G,v);while(w!=0){E++;//此处意味着找到一条边，故累计到变量E中if(visited[w]==FALSE)dfs(G,w);w=nextadj(G,v,w);}}dfs算法中原有的操作合肥工业大学计算机与信息学院288.3.1深度优先搜索遍历intEnum(graphG){inti;E=0;//全局变量E记录整个图中的边数for(i=1;i=n;i++)visited[i]=FALSE;for(i=1;i=n;i++)if(visited[i]==FALSE;)dfs(G,i);returnE/2;}遍历整个图的算法dfs_travel中的原来的部分合肥工业大学计算机与信息学院298.3.1深度优先搜索遍历4.深度遍历算法的应用二例3：设计算法，将1--n(=20,或其他数)放在一个环上，使环上任意两个相邻元素的和为质数。分析：可以用图来描述该问题：①用顶点表示一个数②若两个数的和为质数，则对应顶点之间