Kruskal算法求最优树

关注
Kruskal算法求最优树www.shan-machinery.com练习

一般练习

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是否是二部图,并分析程序的时间复杂度。如有必要可使用堆栈或队列数据结构。

 

 

https://www.shan-machinery.com