北大数据结构与算法课件06图

数据结构与算法第六章图信息科学与技术学院网络与信息系统研究所北京大学信息学院©版权所有，转载或翻印必究Page2主要内容„6.1图的基本概念„6.2图的抽象数据类型„6.3图的存储结构„6.4图的周游（深度、广度、拓扑）„6.5最短路径问题„6.6最小支撑树北京大学信息学院©版权所有，转载或翻印必究Page36.1图的基本概念„G=（V，E）表示„V是顶点（vertex）集合„E是边（edge）的集合„边的始点„边的终点„稀疏图（sparsegraph）„密集图（densegraph）„完全图（completegraph）北京大学信息学院©版权所有，转载或翻印必究Page4无向图„边涉及顶点的偶对无序„实际上是双通北京大学信息学院©版权所有，转载或翻印必究Page5有向图„有向图（directedgraph或digraph）„边涉及顶点的偶对是有序的北京大学信息学院©版权所有，转载或翻印必究Page6„标号图（labeledgraph）„带权图（weightedgraph）北京大学信息学院©版权所有，转载或翻印必究Page7顶点的度（degree）„与该顶点相关联的边的数目„入度(indegree)„出度(outdegree)北京大学信息学院©版权所有，转载或翻印必究Page8子图（subgraph）„图G=(V，E)，G’=(V’，E’)中，若V’≤V，E’≤E，并且E’中的边所关联的顶点都在V’中，则称图G’是图G的子图北京大学信息学院©版权所有，转载或翻印必究Page9路径（path）„从顶点Vp到顶点Vq的路径„顶点序列Vp，Vi1，Vi2，…，Vin，Vq，使得（Vp，Vi1），(Vi1，Vi2)，…，(Vin，Vq)（若对有向图，则使得Vp，Vi1，Vi1，Vi2，…，Vin，Vq）都在E中„简单路径（simplepath）„路径长度（length）VpVq北京大学信息学院©版权所有，转载或翻印必究Page10回路（cycle，也称为环）„无向图中，如果两个结点之间有平行边，容易让人误看作“环”）„路径长度大于等于3„有向图两条边可以构成环，例如V0，V1和V1，V0构成环V0V1√√√╳北京大学信息学院©版权所有，转载或翻印必究Page11„简单回路（simplecycle）„无环图（acyclicgraph）„有向无环图（directedacyclicgraph，简写为DAG）北京大学信息学院©版权所有，转载或翻印必究Page12有根图„一个有向图中，若存在一个顶点V0，从此顶点有路径可以到达图中其它所有顶点，则称此有向图为有根的图，V0称作图的根„树、森林北京大学信息学院©版权所有，转载或翻印必究Page13连通图„对无向图G=（V，E）而言，如果从V1到V2有一条路径（从V2到V1也一定有一条路径），则称V1和V2是连通的（connected）„强连通北京大学信息学院©版权所有，转载或翻印必究Page14连通分支或者连通分量„无向图的最大连通子图„强连通分支（强连通分量）v0v5北京大学信息学院©版权所有，转载或翻印必究Page15网络„带权的连通图北京大学信息学院©版权所有，转载或翻印必究Page16自由树（freetree）„不带有简单回路的无向图，它是连通的，并且具有|V|-1条边北京大学信息学院©版权所有，转载或翻印必究Page176.2图的抽象数据类型„结点、边怎么表示？„结点：增？、删、查?、改„边：增、删、查?、改北京大学信息学院©版权所有，转载或翻印必究Page18classGraph{//图的ADTpublic:intVerticesNum();//返回图的顶点个数intEdgesNum();//返回图的边数//返回与顶点oneVertex相关联的第一条边EdgeFirstEdge(intoneVertex);//返回与边PreEdge有相同关联顶点oneVertex的//下一条边EdgeNextEdge(EdgepreEdge);北京大学信息学院©版权所有，转载或翻印必究Page19//添加一条边boolsetEdge(intfromVertex,inttoVertex,intweight);//删一条边booldelEdge(intfromVertex,inttoVertex);//如果oneEdge是边则返回TRUE，否则返回FALSEboolIsEdge(EdgeoneEdge);//返回边oneEdge的始点intFromVertex(EdgeoneEdge);//返回边oneEdge的终点intToVertex(EdgeoneEdge);//返回边oneEdge的权intWeight(EdgeoneEdge);};北京大学信息学院©版权所有，转载或翻印必究Page206.3图的存储结构„6.3.1图的相邻矩阵（adjacencymatrix）表示法„6.3.2图的邻接表（adjacencylist）表示法„邻接多重表(adjacencymultilist)表示法北京大学信息学院©版权所有，转载或翻印必究Page21„相邻矩阵„表示顶点间相邻关系的矩阵。„若G是一个具有n个顶点的图，则G的相邻矩阵是如下定义的n×n矩阵：A[i,j]=1，若（Vi，Vj）（或Vi，Vj）是图G的边；A[i,j]=0，若（Vi，Vj）（或Vi，Vj）不是图G的边。„相邻矩阵的空间代价为Θ(n2)北京大学信息学院©版权所有，转载或翻印必究Page22A7=1111110000000000010000000⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦北京大学信息学院©版权所有，转载或翻印必究Page23A4=315344000000006156⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦北京大学信息学院©版权所有，转载或翻印必究Page246.3.2图的邻接表（adjacencylist）表示法G6G7北京大学信息学院©版权所有，转载或翻印必究Page25无向图G6邻接表表示北京大学信息学院©版权所有，转载或翻印必究Page26有向图的邻接表G7的出边表G7的入边表北京大学信息学院©版权所有，转载或翻印必究Page27图的邻接表空间代价„n个顶点m条边的无向图„需用(n+2m)个存储单元„n个顶点m条边的有向图„需用(n+m)个存储单元北京大学信息学院©版权所有，转载或翻印必究Page28邻接多重表(adjacencymultilist)„把邻接表表示中代表同一条边的两个表目合为一个表目„图的每条边只用一个多重表表目表示„包括此边的两个顶点的序号„两个指针（一个指针指向与第一个顶点相关联的下一条边，另一个指针指向与第二个顶点相关联的下一条边）北京大学信息学院©版权所有，转载或翻印必究Page29无向图G6的邻接多重表北京大学信息学院©版权所有，转载或翻印必究Page30有向图邻接多重表„在顶点表中设计两个指针„第一个指向以此顶点为始点的第一条边„第二个指向以此顶点为终点的第一条边„边表„第一个指针指向始点与本边始点相同的下一条边„第二个指针指向终点与本边终点相同的下一条边„故仅用表中第一个链便得到有向图的出边表，仅用第二个链便得到有向图的入边表北京大学信息学院©版权所有，转载或翻印必究Page31有向图G7的邻接多重表北京大学信息学院©版权所有，转载或翻印必究Page32„邻接多重表不太常用„在以处理图的边为主，要求每条边处理一次的实际应用中可能有用北京大学信息学院©版权所有，转载或翻印必究Page336.4图的周游„6.4.1深度优先搜索„6.4.2广度优先搜索„6.4.3拓扑排序北京大学信息学院©版权所有，转载或翻印必究Page34森林的周游„按深度方向周游„先根次序„后根次序„按广度方向周游„宽度优先周游„层次周游北京大学信息学院©版权所有，转载或翻印必究Page356.4图的周游（graphtraversal）„给出一个图G和其中任意一个顶点V0„从V0出发系统地访问G中所有的顶点，每个顶点访问一次北京大学信息学院©版权所有，转载或翻印必究Page36图周游的考虑„从一个顶点出发，试探性访问其余顶点，同时必须考虑到下列情况：„从一顶点出发，可能不能到达所有其它的顶点，如非连通图；„也有可能会陷入死循环，如存在回路的图。北京大学信息学院©版权所有，转载或翻印必究Page37„解决办法„为图的每个顶点保留一个标志位（markbit）；„算法开始时，所有顶点的标志位置零；„在周游的过程中，当某个顶点被访问时，其标志位就被标记为已访问。北京大学信息学院©版权所有，转载或翻印必究Page38图的周游算法框架//图的周游算法的实现voidgraph_traverse(Graph&G){//对图所有顶点的标志位进行初始化for(inti=0;iG.VerticesNum();i++)G.Mark[i]=UNVISITED;//检查图的所有顶点是否被标记过，如果未被标记，//则从该未被标记的顶点开始继续周游//do_traverse函数用深度优先或者广度优先for(inti=0;iG.VerticesNum();i++)if(G.Mark[i]==UNVISITED)do_traverse(G,i);}北京大学信息学院©版权所有，转载或翻印必究Page39图的生成树„图的所有顶点加上周游过程中经过的边所构成的子图称作图的生成树„图的生成森林北京大学信息学院©版权所有，转载或翻印必究Page406.4.1深度优先搜索„深度优先搜索（depth-firstsearch，简称DFS）基本思想„访问一个顶点V，然后访问该顶点邻接到的未被访问过的顶点V’„再从V’出发递归地按照深度优先的方式周游„当遇到一个所有邻接于它的顶点都被访问过了的顶点U时，则回到已访问顶点序列中最后一个拥有未被访问的相邻顶点的顶点W„再从W出发递归地按照深度优先的方式周游„最后，当任何已被访问过的顶点都没有未被访问的相邻顶点时，则周游结束„深度优先搜索树（depth-firstsearchtree）北京大学信息学院©版权所有，转载或翻印必究Page41深度优先搜索的顺序是a，b，c，f，d，e，g北京大学信息学院©版权所有，转载或翻印必究Page42从一个顶点出发的深度优先搜索voidDFS(Graph&G,intV){//深度优先搜索算法实现G.Mark[V]=VISITED;//访问顶点V，并标记其标志位PreVisit(G,V);//访问Vfor(Edgee=G.FirstEdge(V);G.IsEdge(e);e=G.NextEdge(e))//访问V邻接到的未被访问过的顶点，并递归地按照//深度优先的方式进行周游if(G.Mark[G.ToVertices(e)]==UNVISITED)DFS(G,G.ToVertices(e));PostVisit(G,V);//访问V}北京大学信息学院©版权所有，转载或翻印必究Page436.4.2广度优先搜索„广度优先搜索（breadth-firstsearch，简称BFS）的基本思想„访问顶点V0，„然后访问V0邻接到的所有未被访问过的顶点V01，V02，…V0i，„再依次访问V01，V02，…V0i邻接到的所有未被访问的顶点，„如此进行下去，直到访问遍所有的顶点。„广度优先搜索树（breadth-firstsearchtree）北京大学信息学院©版权所有，转载或翻印必究Page44广度优先搜索的顺序是a，b，d，e，f，c，g北京大学信息学院©版权所有，转载或翻印必究Page45voidBFS(Graph&G,intV){//广度优先搜索//初始化广度优先周游要用到的队列usingstd::queue;queueintQ;//访问顶点V，并标记其标志位，V入队G.Mark[V]=VISITED;Visit(G,V);Q.push(V);while(!Q.empty()){//如果队列仍然有元素intV=Q.front();Q.pop();//顶部元素出队//将与该点相邻的