第七章 图：图是比线性表和树更为复杂的一种数据结构，在图中，每个结点可以和其他任何结点相关联，而现实世界中许多非数值的问题都可以抽象为图的的问题。在本章中，我们将学到图的基本概念和两种最常用的邻接矩阵和邻接表这两种存储结构；图的运算介绍深度和广度优先搜索遍历；在生成树中将介绍和分析Prim和Kruskal两种经典算法；最短路径将介绍和讲解Dijkstra和Floyd算法；在应用方面将讲解拓扑排序。7.1基本概念:本节介绍了图、有向图和无向图、图和子图、路径和回路、连通图、顶点的度、完全图的概念，和图的表示方法及相关术语。[判断题]邻接表比邻接矩阵更节省空间。
7.2图的存储结构:本节讲解了邻接矩阵的创建及遍历的算法。图的邻接矩阵表示法是用一个二维数组来表示图中顶点之间的相邻关系，N个顶点的邻接矩阵就是一个N阶方阵。邻接表是图的一种链式存储结构，适合存储稀疏图，本节主要讲解了邻接表的创建、查找和输出等算法。
7.3图的遍历算法及其应用:根据搜索路径的方向不同，对图的遍历有深度优先搜索遍历和广度优先搜索遍历两种方法，这是许多图算法的基础，许多问题的求解可以转化为这两种算法及其变形形式。本节通过非连通图的遍历算法、设计算法以求解无向图G的连通分量的个数、设计算法求出无向图G的边数这几个算法讲解了图的应用问题。
7.4最小生成树:在图论中，常常将树定义为一个无回路连通图，而生成树是连通图的极小连通子图。Prim算法使用MST性质构造了最小生成树，设计了如何找到连接u和V-U的最短边来扩充生成树T的算法。构造最小生成树的另一个算法是由克鲁斯卡尔(Kruskal)提出的，按照长度递增的顺序依次选择图中的边，如果该边满足件，则可扩充到生成树中，直到所有的结点都在同一连通分量中为止。
7.5最短路径:求解两点之间的最短路径的问题也是图的典型应用问题之一，本节主要讲解了迪杰斯特拉（Dijkstra）算法求解单源最短路径的问题。求解图中任意两个顶点之间的最短路径，可以依次把有向网络的每个顶点作为源点，重复调用n次DIJKSTRA算法是一种解决方案，而本节所介绍的弗洛伊德(Floyd)算法是使用递推的方式求解多源最短路径。
7.6拓扑排序:可以用有向图中的顶点来表示活动, 弧表示活动之间的优先关系, 这样的有向图称为 (Activity On Vertex network) ，简称为AOV网。本节主要讲解了AOV网的拓扑序列算法，求解整个工程得以顺利完成的一种可行方案。
选项:[对, 错]
[判断题]任意一个AOV网都可以有拓扑排序。
选项:[错, 对]
[判断题]任一AOV网中至少有一条关键路径，且是从源点到汇点的路径中最长的一条。（ ）
选项:[错, 对]
[判断题]若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。
选项:[错, 对]
[单选题]带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（ ）。
选项:[第i行非∞的元素之和, 第i行非∞且非0的元素个数, 第i列非∞且非0的元素个数, 第i列非∞的元素之和]
[单选题]用 Prim和Kruskal两种算法构造同一连通图的最小生成树，所得的最小生成树（ ）。选项:[可能相同也可能不同 , 是不同的, 是相同的, 其余都不对]
[单选题]如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点，则该图一定是（ ）。选项:[有回路的图, 一棵树, 连通图, 完全图]
[单选题]深度优先遍历类似于二叉树的（ ）。选项:[层次遍历, 先序遍历, 后序遍历, 中序遍历]
[单选题]用邻接表存储图所用的空间大小（ ）。选项:[与图的顶点和边数与关, 只与图的顶点数与关, 与边数的平方有关, 只与图的边数有关]
[单选题]设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（ ）。选项:[O(n+e), O(n3), O(n2), O(ne)]
[单选题]以下对AOV网的描述中，错误的是（ ）。选项:[所有关键活动都提前完成，整个工程也将提前完成。, 在AOV网中可能存在多条关键路径。, 任何一个关键活动提前完成，整个工程也将提前完成。, 关键活动不近期完成就会影响整个工程的完成时间。]
[单选题]设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（ ）条有向边。选项:[m, n-1, n, m-1]
[单选题]
具有n个顶点的无向完全图的边数为（ ）。
选项:[n2, n(n-1)/2, n2-1, n(n-1)][判断题]图的广度优先遍历算法中用到的辅助队列，每个顶点最多进队的次数不确定。
选项:[错, 对]
[单选题]对含有n个顶点e条边的有向图，Floyd算法的时间复杂度为（ ）选项:[ O(n2), O(n3), O(ne), O(n)]
温馨提示支付 ￥1.00 元后可查看付费内容,请先翻页预览!
