数据结构第8章1
需积分: 0 187 浏览量
2022-08-08
19:41:28
上传
评论
收藏 632KB DOCX 举报
158
第 8 章 图
一、复习要点
图是一种重要的非线性结构。它的特点是每一个顶点都可以与其它顶点相关联，与树不
同，图中各个顶点的地位都是平等的，对顶点的编号都是人为的。通常，定义图由两个集合
构成：一个是顶点的非空有穷集合，一个是顶点与顶点之间关系(边)的有穷集合。对图的处
理要区分有向图与无向图。它的存储表示可以使用邻接矩阵，可以使用邻接表，前者属顺序
表示，后者属链接表示。在本章着重讨论了图的深度优先搜索和广度优先搜索算法，附带引
入了生成树与生成森林的概念。对于带权图，给出了最小生成树的两种方法：Prim 算法和
Kruskal 算法，后者使用了最小堆和并查集作为它的辅助求解手段。在解决最短路径问题时，
采用了逐步求解的策略。最后讨论了作工程计划时常用的活动网络。涉及的主要概念是拓扑
排序和关键路径，在解决应用问题时它们十分有用。
本章复习的要点是：
1、基本知识点
主要要求理解图的基本概念，包括图的定义、图的连通性、图的路径和路径长度、图中
各顶点的度及度的度量、无向连通图的最大边数和最小边数，有向强连通图的最大边数与最
小边数等。掌握图的存储表示，包括邻接矩阵和邻接表，以及这些存储表示上的典型操作，
如构造、求根、找第一个邻接顶点、找下一个邻接顶点等操作的实现算法。并要求掌握图的
两种遍历算法：深度优先搜索和广度优先搜索算法，以及求解连通性问题的方法。理解求解
关节点及构造重连通图的方法。此外，要求掌握构造最小生成树的 Prim 算法和 Kruskal 方
法，掌握活动网络的拓扑排序算法，掌握求解关键路径的方法。需要注意的是，让某个关键
活动提前完成，是否能让整个工程提前完成。
2、算法设计
建立无向带权图的邻接表的算法，要求输入边的数目随机而定。
图的深度优先搜索的递归算法。
利用图的深度优先搜索的递归算法建立图的深度优先生成森林(用左子女右兄弟表示)
的算法。
图的广度优先搜索算法。
利用图的广度优先搜索算法建立图的广度优先生成森林(用左子女右兄弟表示)的算
法。
求解最小生成树的 Prim 算法，注意 nearvex 和 lowcost 辅助数组的变化。
求解最小生成树的 Kruskal 算法，注意 minheap 和 UFset 的变化。
求解最短路径的 dijkstra 算法，注意 dist 辅助数组的变化。
有向图中求解拓扑排序的算法，要求用邻接表作为图的存储表示。注意算法执行过
程中入度为零的顶点栈的变化。
有向图中求解拓扑排序的算法，要求用邻接矩阵作为图的存储表示。
二、难点和重点
1、图：图的定义与图的存储表示
邻接矩阵表示(通常是稀疏矩阵)
邻接表与逆邻接表表示，要求建立算法
邻接多重表(十字链表)表示
剩余20页未读，继续阅读
资源评论
