清华 殷人昆C++数据结构课件数据结构第8章.doc

《清华 殷人昆C++数据结构课件数据结构第8章.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第8章图一、复习要点图是一种重要的非线性结构。它的特点是每一个顶点都可以与其它顶点相关联，与树不同，图中各个顶点的地位都是平等的，对顶点的编号都是人为的。通常，定义图由两个集合构成：一个是顶点的非空有穷集合，一个是顶点与顶点之间关系(边)的有穷集合。对图的处理要区分有向图与无向图。它的存储表示可以使用邻接矩阵，可以使用邻接表，前者属顺序表示，后者属链接表示。在本章着重讨论了图的深度优先搜索和广度优先搜索算法，附带引入了生成树与生成森林的概念。对于带权图，给出了最小生成树的两种方法：Prim算法和Kruskal算法，后者使用了最小堆和

2、并查集作为它的辅助求解手段。在解决最短路径问题时，采用了逐步求解的策略。最后讨论了作工程计划时常用的活动网络。涉及的主要概念是拓扑排序和关键路径，在解决应用问题时它们十分有用。本章复习的要点是：1、基本知识点主要要求理解图的基本概念，包括图的定义、图的连通性、图的路径和路径长度、图中各顶点的度及度的度量、无向连通图的最大边数和最小边数，有向强连通图的最大边数与最小边数等。掌握图的存储表示，包括邻接矩阵和邻接表，以及这些存储表示上的典型操作，如构造、求根、找第一个邻接顶点、找下一个邻接顶点等操作的实现算法。并要求掌握图的两种遍历算法：

3、深度优先搜索和广度优先搜索算法，以及求解连通性问题的方法。理解求解关节点及构造重连通图的方法。此外，要求掌握构造最小生成树的Prim算法和Kruskal方法，掌握活动网络的拓扑排序算法，掌握求解关键路径的方法。需要注意的是，让某个关键活动提前完成，是否能让整个工程提前完成。2、算法设计Ø建立无向带权图的邻接表的算法，要求输入边的数目随机而定。Ø图的深度优先搜索的递归算法。Ø利用图的深度优先搜索的递归算法建立图的深度优先生成森林(用左子女右兄弟表示)的算法。Ø图的广度优先搜索算法。Ø利用图的广度优先搜索算法建立图的广度优先生成森林(用

4、左子女右兄弟表示)的算法。Ø求解最小生成树的Prim算法，注意nearvex和lowcost辅助数组的变化。Ø求解最小生成树的Kruskal算法，注意minheap和UFset的变化。Ø求解最短路径的dijkstra算法，注意dist辅助数组的变化。Ø有向图中求解拓扑排序的算法，要求用邻接表作为图的存储表示。注意算法执行过程中入度为零的顶点栈的变化。Ø有向图中求解拓扑排序的算法，要求用邻接矩阵作为图的存储表示。二、难点和重点1、图：图的定义与图的存储表示Ø邻接矩阵表示(通常是稀疏矩阵)Ø邻接表与逆邻接表表示，要求建立算法Ø邻接多重表

5、(十字链表)表示2、深度优先遍历与广度优先遍历Ø生成树与生成树林的定义Ø深度优先搜索算法和广度优先搜索算法Ø深度优先搜索是个递归的过程，而广度优先搜索是个非递归的过程Ø为防止重复访问已经访问过的顶点，需要设置一个访问标志数组visited3、图的连通性Ø深度优先搜索可以遍历一个连通分量上的所有顶点Ø对非连通图进行遍历，可以建立一个生成森林Ø对非强连通图进行遍历，可能建立一个生成森林Ø关节点的求解方法和以最少的边构成重连通图的方法4、最小生成树Ø对于连通网络、可用不会构成环路的权值最小的n-1条边构成最小生成树Ø会画出用Kruskal

6、算法及Prim算法构造最小生成树的过程5、单源最短路径Ø采用逐步求解的方式求某一顶点到其他顶点的最短路径的方法Ø要求每条边的权值必须大于零6、活动网络Ø拓扑排序、关键路径、关键活动、AOE网Ø拓扑排序将一个偏序图转化为一个全序图。Ø为实现拓扑排序，要建立一个栈，将所有入度为零的顶点进栈Ø关键路径的计算三、教材中习题的解析8-1画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n个顶点的无向完全图中，边的条数为n(n-1)/2。【解答】2个顶点的无向完全图1个顶点的无向完全图5个顶点的无向完全图4个顶点的无向完

7、全图3个顶点的无向完全图【证明】在有n个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有n-1条边与其他n-1个顶点相连，总计n个顶点有n(n-1)条边。但在无向图中，顶点i到顶点j与顶点j到顶点i是同一条边，所以总共有n(n-1)/2条边。ABCDEF8-2右边的有向图是强连通的吗？请列出所有的简单路径。【解答】判断一个有向图是否强连通，要看从任一顶点出发是否能够回到该顶点。右面的有向图做不到这一点，它不是强连通的有向图。各个顶点自成强连通分量。所谓简单路径是指该路径上没有重复的顶点。从顶点A出发，到其

8、他的各个顶点的简单路径有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。从顶点B出发，到其他各个顶点的简单