数据结构第8章-图

158第8章图一、复习要点图是一种重要的非线性结构。它的特点是每一个顶点都可以与其它顶点相关联，与树不同，图中各个顶点的地位都是平等的，对顶点的编号都是人为的。通常，定义图由两个集合构成：一个是顶点的非空有穷集合，一个是顶点与顶点之间关系(边)的有穷集合。对图的处理要区分有向图与无向图。它的存储表示可以使用邻接矩阵，可以使用邻接表，前者属顺序表示，后者属链接表示。在本章着重讨论了图的深度优先搜索和广度优先搜索算法，附带引入了生成树与生成森林的概念。对于带权图，给出了最小生成树的两种方法：Prim算法和Kruskal算法，后者使用了最小堆和并查集作为它的辅助求解手段。在解决最短路径问题时，采用了逐步求解的策略。最后讨论了作工程计划时常用的活动网络。涉及的主要概念是拓扑排序和关键路径，在解决应用问题时它们十分有用。本章复习的要点是：1、基本知识点主要要求理解图的基本概念，包括图的定义、图的连通性、图的路径和路径长度、图中各顶点的度及度的度量、无向连通图的最大边数和最小边数，有向强连通图的最大边数与最小边数等。掌握图的存储表示，包括邻接矩阵和邻接表，以及这些存储表示上的典型操作，如构造、求根、找第一个邻接顶点、找下一个邻接顶点等操作的实现算法。并要求掌握图的两种遍历算法：深度优先搜索和广度优先搜索算法，以及求解连通性问题的方法。理解求解关节点及构造重连通图的方法。此外，要求掌握构造最小生成树的Prim算法和Kruskal方法，掌握活动网络的拓扑排序算法，掌握求解关键路径的方法。需要注意的是，让某个关键活动提前完成，是否能让整个工程提前完成。2、算法设计建立无向带权图的邻接表的算法，要求输入边的数目随机而定。图的深度优先搜索的递归算法。利用图的深度优先搜索的递归算法建立图的深度优先生成森林(用左子女右兄弟表示)的算法。图的广度优先搜索算法。利用图的广度优先搜索算法建立图的广度优先生成森林(用左子女右兄弟表示)的算法。求解最小生成树的Prim算法，注意nearvex和lowcost辅助数组的变化。求解最小生成树的Kruskal算法，注意minheap和UFset的变化。求解最短路径的dijkstra算法，注意dist辅助数组的变化。有向图中求解拓扑排序的算法，要求用邻接表作为图的存储表示。注意算法执行过程中入度为零的顶点栈的变化。有向图中求解拓扑排序的算法，要求用邻接矩阵作为图的存储表示。二、难点和重点1、图：图的定义与图的存储表示邻接矩阵表示(通常是稀疏矩阵)邻接表与逆邻接表表示，要求建立算法邻接多重表(十字链表)表示1592、深度优先遍历与广度优先遍历生成树与生成树林的定义深度优先搜索算法和广度优先搜索算法深度优先搜索是个递归的过程，而广度优先搜索是个非递归的过程为防止重复访问已经访问过的顶点，需要设置一个访问标志数组visited3、图的连通性深度优先搜索可以遍历一个连通分量上的所有顶点对非连通图进行遍历，可以建立一个生成森林对非强连通图进行遍历，可能建立一个生成森林关节点的求解方法和以最少的边构成重连通图的方法4、最小生成树对于连通网络、可用不会构成环路的权值最小的n-1条边构成最小生成树会画出用Kruskal算法及Prim算法构造最小生成树的过程5、单源最短路径采用逐步求解的方式求某一顶点到其他顶点的最短路径的方法要求每条边的权值必须大于零6、活动网络拓扑排序、关键路径、关键活动、AOE网拓扑排序将一个偏序图转化为一个全序图。为实现拓扑排序，要建立一个栈，将所有入度为零的顶点进栈关键路径的计算三、教材中习题的解析8-1画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n个顶点的无向完全图中，边的条数为n(n-1)/2。【解答】【证明】在有n个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有n-1条边与其他n-1个顶点相连，总计n个顶点有n(n-1)条边。但在无向图中，顶点i到顶点j与顶点j到顶点i是同一条边，所以总共有n(n-1)/2条边。8-2右边的有向图是强连通的吗？请列出所有的简单路径。【解答】判断一个有向图是否强连通，要看从任一顶点出发是否能够回到该顶点。右面的有向图做不到这一点，它不是强连通的有向图。各个顶点自成强连通分量。所谓简单路径是指该路径上没有重复的顶点。从顶点A出发，到其他的各个顶点的简单路径有A→B，A→D→B，A→B→C，A→D→B→C，A→D，A→B→E，A→D→E，A→D→B→E，A→B→C→F→E，A→D→B→C→F→E，A→B→C→F，A→D→B→C→F。1个顶点的无向完全图2个顶点的无向完全图3个顶点的无向完全图4个顶点的无向完全图5个顶点的无向完全图ABCDEF160010000000000010010100000010100001010Edge从顶点B出发，到其他各个顶点的简单路径有B→C，B→C→F，B→E，B→C→F→E。从顶点C出发，到其他各个顶点的简单路径有C→F，C→F→E。从顶点D出发，到其他各个顶点的简单路径有D→B，D→B→C，D→B→C→F，D→E，D→B→E，D→B→C→F→E。从顶点E出发，到其他各个顶点的简单路径无。从顶点F出发，到其他各个顶点的简单路径有F→E。8-3给出右图的邻接矩阵、邻接表和邻接多重表表示。【解答】(1)邻接矩阵(2)邻接表(3)邻接多重表（十字链表）0A1B2C3D4E5F03101352∧∧∧∧∧∧（出边表）（入边表）datafinfoutijilinkjlink∧∧∧∧∧∧∧ABCDEF3245144∧∧∧∧∧∧10A1B2C3D4E5F∧∧0A1B2C3D4E5F03(A,D)31(D,B)∧∧01(A,B)12(B,C)14(B,E)54(F,E)34(D,E)25(C,F)161或8-4用邻接矩阵表示图时，若图中有1000个顶点，1000条边，则形成的邻接矩阵有多少矩阵元素？有多少非零元素？是否稀疏矩阵？【解答】一个图中有1000个顶点，其邻接矩阵中的矩阵元素有10002=1000000个。它有1000个非零元素（对于有向图）或2000个非零元素（对于无向图），因此是稀疏矩阵。8-5用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？【解答】用邻接矩阵表示图，矩阵元素的个数是顶点个数的平方，与边的条数无关。矩阵中非零元素的个数与边的条数有关。8-6有n个顶点的无向连通图至少有多少条边？有n个顶点的有向强连通图至少有多少条边？试举例说明。【解答】n个顶点的无向连通图至少有n-1条边，n个顶点的有向强连通图至少有n条边。例如：特例情况是当n=1时，此时至少有0条边。8-7对于有n个顶点的无向图，采用邻接矩阵表示，如何判断以下问题：图中有多少条边？任意两个顶点i和j之间是否有边相连？任意一个顶点的度是多少？【解答】用邻接矩阵表示无向图时，因为是对称矩阵，对矩阵的上三角部分或下三角部分检测一遍，统计其中的非零元素个数，就是图中的边数。如果邻接矩阵中A[i][j]不为零，说明顶点i与顶点j之间有边相连。此外统计矩阵第i行或第i列的非零元素个数，就可得到顶点i的度数。8-8对于如右图所示的有向图，试写出：(1)从顶点①出发进行深度优先搜索所得到的深度优先生成树；(2)从顶点②出发进行广度优先搜索所得到的广度优先生成树；【解答】(1)以顶点①为根的深度优先生成树（不唯一）：②③④⑤⑥(2)以顶点②为根的广度优先生成树：①②③④⑤①②③④⑤①②③④⑤①②③④⑤1628-9试扩充深度优先搜索算法，在遍历图的过程中建立生成森林的左子女-右兄弟链表。算法的首部为voidGraph::DFS(constintv,intvisited[],TreeNodeint*t)其中，指针t指向生成森林上具有图顶点v信息的根结点。（提示：在继续按深度方向从根v的某一未访问过的邻接顶点w向下遍历之前，建立子女结点。但需要判断是作为根的第一个子女还是作为其子女的右兄弟链入生成树。）【解答】为建立生成森林，需要先给出建立生成树的算法，然后再在遍历图的过程中，通过一次次地调用这个算法，以建立生成森林。templateTypevoidGraphType::DFS_Tree(constintv,intvisited[],TreeNodeType*t){//从图的顶点v出发,深度优先遍历图,建立以t(已在上层算法中建立)为根的生成树。Visited[v]=1;intfirst=1;TreeNodeType*p,*q;intw=GetFirstNeighbor(v);//取第一个邻接顶点while(w!=-1){//若邻接顶点存在if(vosited[w]==0){//且该邻接结点未访问过p=newTreeNodeType(GetValue(w));//建立新的生成树结点if(first==1)//若根*t还未链入任一子女{t-setFirstChild(p);first=0;}//新结点*p成为根*t的第一个子女elseq-setNextSibling(p);//否则新结点*p成为*q的下一个兄弟q=p;//指针q总指示兄弟链最后一个结点DFS_Tree(w,visited,q);//从*q向下建立子树}w=GetNextNeighbor(v,w);//取顶点v排在邻接顶点w的下一个邻接顶点}}下一个算法用于建立以左子女-右兄弟链表为存储表示的生成森林。templateTypevoidGraphType::DFS_Forest(TreeType&T){//从图的顶点v出发,深度优先遍历图,建立以左子女-右兄弟链表表示的生成森林T。T.root=NULL;intn=NumberOfVertices();//顶点个数TreeNodeType*p,*q;int*visited=newint[n];//建立访问标记数组for(intv=0;vn;v++)visited[v]=0;for(v=0;vn;v++)//逐个顶点检测if(visited[v]==0){//若尚未访问过p=newTreeNodeType(GetValue(v));//建立新结点*pif(T.root==NULL)T.root=p;//原来是空的生成森林,新结点成为根elseq-setNextSibling(p);//否则新结点*p成为*q的下一个兄弟q=p;DFS_Tree(v,visited,p);//建立以*p为根的生成树}}8-10用邻接表表示图时，顶点个数设为n，边的条数设为e，在邻接表上执行有关图的遍历操作时，时间代价是O(n*e)？还是O(n+e)？或者是O(max(n,e))？【解答】在邻接表上执行图的遍历操作时，需要对邻接表中所有的边链表中的结点访问一次，还163需要对所有的顶点访问一次，所以时间代价是O(n+e)。8-11右图是一个连通图，请画出(1)以顶点①为根的深度优先生成树；(2)如果有关节点，请找出所有的关节点。(3)如果想把该连通图变成重连通图，至少在图中加几条边？如何加？【解答】(1)以顶点①为根的深度优先生成树：(2)关节点为①,②,③,⑦,⑧(3)至少加四条边(1,10),(3,4),(4,5),(5,6)。从③的子孙结点⑩到③的祖先结点①引一条边，从②的子孙结点④到根①的另一分支③引一条边，并将⑦的子孙结点⑤、⑥与结点④连结起来，可使其变为重连通图。8-12试证明在一个有n个顶点的完全图中，生成树的数目至少有2n-1-1。【证明】略8-13编写一个完整的程序，首先定义堆和并查集的结构类型和相关操作，再定义Kruskal求连通网络的最小生成树算法的实现。并以右图为例，写出求解过程中堆、并查集和最小生成树的变化。【解答】求解过程的第一步是对所有的边，按其权值大小建堆：5①②③④⑤⑥117681097⑩①②③④⑤⑥⑦⑧⑨⑩①②③④⑤⑥⑦⑧⑨1271