练习

一般练习

1.         复习下面概念：图，二元关系，拓扑结构，图论，图算法，顶点和边，有向图和无向图，有向边及其始点和终点，无向边，邻接（顶）点，邻接边，邻接关系，完全图，顶点的度，入度和出度，路径，路径的长度，回路（环），简单回路，简单路径，有根图，连通，连通无向图（连通图），强连通有向图，最小连通图，最小有根图，无向树，有向树，子图，（无向图的）连通子图，（有向图的）强连通子图，极大连通子图（连通分量），极大强连通子图（强连通分量），带权图，网络，邻接矩阵，顶点表，邻接表表示法，图的遍历（周游），可达顶点，深度优先遍历和宽度优先遍历，深度优先搜索（DFS）序列，宽度优先搜索（BFS）序列，生成树，DFS生成树，BFS生成树，（网络的）最小生成树，Kruskal算法，连通分量的代表元，Prim算法，MST性质，最短路径问题，带权图上的路径长度，Dijkstra算法，Floyd算法，AOV网，拓扑序列和拓扑排序，制约关系，AOE网（一类带权有向图），关键路径。

2.         设有向图，其中，，请

a)         画出这个有向图；

b)        给出其邻接矩阵表示；

c)         给出其邻接表表示；

d)        判断这个图是否强连通；如果强连通，请给出一个经过图中所有顶点的环路；如果不是强连通的，请给出其中的各个强连通分量。

3.         如果有向图用邻接矩阵表示，如何回答下面问题：

a)         图中共有多少条边？

b)        从一个顶点到另一顶点是否有边？

c)         一个顶点的出度？

d)        一个顶点的入度？

4.         假设一个图包含n个顶点，如果是无向图最多有几条边？有向图呢？

5.         一个包含n个顶点的连通（无向）图最少有几条边？一个包含n个顶点的强连通（有向）图最少包含几条边？

6.         设n个顶点的无向图中的边恰好形成一个环路，该图有多少棵不同的生成树？

7.         图7.16的有向图包含几个强连通分量？

8.         请求出图7.16有向图里从结点v0到v9的所有简单路径。

9.         在Kruskal算法中需要不断选择最短边。7.4.2节开始提出了几种可能做法。请分析它们各自的优缺点，计算其复杂度。

10.     图7.17给出了一个带权无向图，请针对它完成下面工作：

a)         做出其邻接矩阵；

b)        做出其邻接表表示；

c)         将其看作简单的无向图，用深度优先搜索方法求出其DFS序列和DFS生成树；

d)        用宽度优先搜索方法求出其BFS序列和BFS生成树；

e)         用Kruskal算法求出其最小生成树（不一定唯一性）；

f)         用Prim算法求出其最小生成树。

11.     图7.16给出的是一个带权有向图。请用Dijkstra算法求出图中从v0出发到其他顶点的最短路径。

12.     请求出图7.18中从顶点v0出发的两个不同的拓扑排序序列。

13.     图7.18给出了一个带权有向图，请求出图中从v0到v9的所有关键活动和关键路径。

14.     给定（有向或无向）图G和图中两个顶点u和v，要求确定是否存在从u到v的路径，请设计解决这个问题的算法。

15.     请设计一个算法，检查给定的有向图G中是否存在回路，并在G存在回路的情况时用给出一条回路。要求算法的复杂性为O(n2)。

16.     请设计一个算法，求出不带权的无向连通图中距离顶点v0的最短路径长度（即路径上的边数）为L的所有顶点，要求尽可能高效。

17.     无环的连通无向图  的直径是图中所有顶点对之间最短路径长度的最大值，即，的直径 ，其中  表示顶点u与顶点v之间最短路径的长度（即两者间最短路径包含的边数）。请设计一个算法求无环的连通无向图的直径，并分析算法的时间复杂度。

编程练习

1.         请按7.2节开始处的建议，基于Python字典定义一种图类型，实现图抽象数据类型中给出的所有基本操作。请分析各种操作的时间和空间复杂度，并比较这种实现技术与7.2节给出的图的邻接矩阵实现和邻接表实现。在分析和比较中，请特别关注本章考虑的各种算法的实现效率。

2.         在7.2.1节里提出了记录已构造的出边表的想法。请仔细研究这个问题，提出一套可行的实现方法，并完成实现这种功能。

3.         为7.2.1节定义的图类增加其他有用操作，例如前面习题提到的确定顶点间路径的操作，检查图中是否存在回路并可能给出回路的操作等。

4.         修改7.2.2节的基于邻接表技术的图类，用自定义的链表实现邻接表。

5.         第7.2节最后讨论了图中顶点可能关联一些信息，建议给图对象扩充一个顶点表（或顶点字典）。请修改某个图类的定义，实现这种想法。在做这项工作时，请给图对象增加一些使用顶点的有用操作。

6.         请参考7.3.1节给出的深度优先图遍历算法，设计并实现其他（递归的或非递归的）深度优先和宽度优先遍历算法。

7.         请实现遍历图结点和图中边的迭代器。有关的迭代器应返回什么值？

8.         请实现构造BFS生成树的算法，以及构造DFS生成树的非递归算法。

9.         第7.4.2节提出了几种选择最小元素的方法，给出的算法中采用了其中一种。请修改算法的实现，采用另一种不同的选取方法。

10.     实现第7.4.4节所需的可减权堆DecPrioHeap，支持所需操作，并论证所做实现具有文中提出的操作复杂性。

11.     请基于可减权堆重新实现Dijkstra算法，保证算法在不付出更大时间代价的情况下，空间复杂度变成O(|V|)。

12.     在toposort函数里另用一个表toposeq记录找到的拓扑序列。实际上这个表不必要，完全可以在indegree表里记录拓扑序列。请考虑这种可能性，考虑是否需要约定从结果表中得到拓扑序列的方法。考虑如何修改原函数实现这种可能性。需要付出多少时间代价？算法的时间复杂性会改变吗？

13.     二部图（bipartite graph）G = (V，E) 是一类无向图，其顶点集V可以划分为两个不相交子集V1和V2 = V-V1，使V1中的任意两顶点在图G中不相邻，且V2中任意两顶点在G中不相邻。换句话说，图中任一条边的两端均分属这两个顶点集。

a)         请举出一个结点个数为7的二部图和一个结点数为7的非二部图。

b)        请用定义函数bigraph判断无向图G是否是二部图，并分析程序的时间复杂度。如有必要可使用堆栈或队列数据结构。