第七章 图：图是一种逻辑关系更为复杂的一种逻辑结构，其应用十分广泛。本章首先介绍图的基本概念和有关术语，介绍图的两种存储方式（邻接矩阵、邻接表），接着学习图的两种遍历算法（图的深度和广度优先遍历）以及最小生成树的构造（普里姆算法和克鲁斯卡尔算法），最后学习最短路径（Dijkstra算法和Floyd算法）和拓扑排序和关键路径；7.1图的概念与性质:要学习图的算法，首先必须了解图的概念及相关术语。本节介绍图的定义和有关图的一些术语以及图的一些基本性质。[多选题]下列哪些算法是属于图的应用算法（ ）
7.2图的存储:图在计算机中的存储有多种方案，本节主要介绍图的邻接矩阵以及邻接表存储。由于图的各种操作实现均依赖于其存储结构，因此要求理解并掌握这两种不同存储结构的特点。
7.3图的深度遍历:图的遍历是图的许多操作的基础。图的常用的两种遍历方法是深度优先搜索和广度遍历。本节主要学习深度优先遍历的算法思想，并介绍了基于邻接矩阵和邻接表的深度优先遍历的实现。
7.4图的广度遍历:图的常用两种遍历方法是深度优先搜索和广度优先搜索。本节主要学习广度优先遍历策略的算法思想，并介绍了基于邻接矩阵和邻接表的广度优先遍历的实现。
7.5最小生成树-prim算法:在图的广泛应用中，一个非常常见的应用是构造最小生成树。Prim算法是一种构造连通图的最小生成树的贪心算法，本节主要学习Prim的算法思想及其算法实现。
7.6最小生成树-kruskal算法:Kruskal算法是另一种构造连通图的最小生成树的算法，本节介绍Kruskal算法思想以及算法实现。
7.7单源最短路径-Dijkstra算法:在许多图的应用中，另一个常见的应用就是找最短路径，其中一个就是求单源最短路径，即寻求从图的某个顶点出发到其余各顶点的最短路径。本节主要介绍Dijkstra算法的思想及算法实现。
7.8两点之间最短路径-Floyd算法:Floyd算法主要用于构造图中任意两点间的最短路径。本节主要介绍Floyd算法思想及其算法实现。
7.9拓扑排序:一个大的工程能否顺利完工，其中一个关键问题是在其所有子工程构成的AOV网中能否确定一个顶点的拓扑序列。本节介绍拓扑序列的构造思想以及算法实现。
7.10关键路径:关键路径
7.11图的应用:图的应用
哈夫曼（Huffman）算法
克鲁斯卡尔（Kruskal）算法
欧几里德算法
拓扑排序算法
迪杰斯特拉（Dijkstra）算法
答案：克鲁斯卡尔（Kruskal）算法迪杰斯特拉（Dijkstra）算法拓扑排序算法
[多选题]下列（ ）算法可用于构造图的生成树。
kruskal
DFS
Floyd
Prim
BFS[多选题]下列（ ）是构造最短路径的方法。
Prim
Floyd
BFS
Dijkstra
Kruskal[判断题]n个结点的无向图，若没有顶点到自身的边，也没有一个顶点到另一个顶点的多重边，此时若有n(n-1)/2条边 ，则该无向图一定是连通图。
对
错[判断题]用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用空间大小与图的顶点数有关，与图的边数无关。
错
对[判断题]对于任意一个图，从它的某个顶点出发进行一次深度或者广度遍历可以访问到该图的每个顶点。
对
错[判断题]对于无向图的生成树，从同一顶点出发所得的生成树相同。
错
对[判断题]有向图顶点v的度是其邻接矩阵中第v行1的个数。
错
对[单选题]无向图的邻接矩阵是（ ）矩阵。
对称
上三角阵
稀疏矩阵
下三角阵[单选题]用邻接表存储的图所用空间大小（ ）
与图的顶点数和边数都有关
只与图的边数有关
与边数的平方有关
只与图的顶点数有关与边数的平方有关[单选题]不论基于图的邻接表还是基于邻接矩阵存储，图的广度优先遍历算法类似于树的（ ）
先序遍历
中序遍历
层次遍历
后序遍历[单选题]一个连通图的生成树是包含该图的所有顶点的（ ）
极大子图
极大连通子图
极小子图
极小连通子图[单选题]具有n个顶点的连通有向图中，至少需要（ ）条边。
n
n+1
2n
n-1
温馨提示支付 ￥1.00 元后可查看付费内容,请先翻页预览!
