已知一个图的顶点集V和边集E分别为:V- {1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。

克鲁斯卡尔算法是一种基于贪心策略的最小生成树算法。下面是使用克鲁斯卡尔算法得到最小生成树的过程：

1. 将边集E按照权值从小到大排序，得到新的边集E'；
2. 从E'中依次取出权值最小的边，如果这条边的两个端点不在同一个集合中，则将这条边加入最小生成树的边集中，并将这两个端点所在的集合合并成一个集合。重复这个过程，直到最小生成树中包含V中的所有顶点；
3. 最终得到的最小生成树的边集即为依次得到的各条边。

按照这个过程，我们可以得到最小生成树中依次得到的各条边为：

(4,6) 4

(1,2) 3

(3,6) 9

(2,3) 6

(2,5) 10

(5,6) 18

(1,4) 8

相关问题

已知一个图的顶点集V和边集E分别为:V- {1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克鲁斯卡尔算法得到最小生成树,试写出在最小生成树中

包含的边以及它们的权值。

首先，将边按照权值从小到大排序，得到如下排序后的边集：

{(4,6)4, (1,2)3, (1,3)5, (2,3)6, (3,6)9, (2,5)10, (3,5)12, (5,6)18, (4,7)20}

从权值最小的边(4,6)4开始，逐一加入边，如果加入一条边会形成回路，则不加入，直到加入n-1条边为止，其中n为顶点数。

首先加入(4,6)4，得到生成树T={(4,6)4}，其中顶点集为{4,6}。

接下来加入(1,2)3，这条边与T不形成回路，加入后得到T={(4,6)4, (1,2)3}，其中顶点集为{1,2,4,6}。

继续加入(1,3)5，这条边与T不形成回路，加入后得到T={(4,6)4, (1,2)3, (1,3)5}，其中顶点集为{1,2,3,4,6}。

接着加入(2,3)6，这条边与T不形成回路，加入后得到T={(4,6)4, (1,2)3, (1,3)5, (2,3)6}，其中顶点集为{1,2,3,4,6}。

加入(3,6)9，这条边与T不形成回路，加入后得到T={(4,6)4, (1,2)3, (1,3)5, (2,3)6, (3,6)9}，其中顶点集为{1,2,3,4,6}。

加入(2,5)10，这条边与T不形成回路，加入后得到T={(4,6)4, (1,2)3, (1,3)5, (2,3)6, (3,6)9, (2,5)10}，其中顶点集为{1,2,3,4,5,6}。

加入(3,5)12，这条边与T不形成回路，加入后得到T={(4,6)4, (1,2)3, (1,3)5, (2,3)6, (3,6)9, (2,5)10, (3,5)12}，其中顶点集为{1,2,3,4,5,6}。

加入(5,6)18，这条边与T不形成回路，加入后得到T={(4,6)4, (1,2)3, (1,3)5, (2,3)6, (3,6)9, (2,5)10, (3,5)12, (5,6)18}，其中顶点集为{1,2,3,4,5,6}。

最后加入(4,7)20，这条边与T不形成回路，加入后得到T={(4,6)4, (1,2)3, (1,3)5, (2,3)6, (3,6)9, (2,5)10, (3,5)12, (5,6)18, (4,7)20}，其中顶点集为{1,2,3,4,5,6,7}。

因此，最小生成树包含的边以及它们的权值为：

(4,6)4, (1,2)3, (1,3)5, (2,3)6, (3,6)9, (2,5)10, (3,5)12, (5,6)18, (4,7)20

9. 已知一个图的顶点集V和边集E分别为： V={1,2,3，4,5，6，7}; E=｛〈2，1>,〈3，2>，〈3，6〉,〈4，3〉,<4,5>,<4,6>,〈5,1>,<5,7〉,〈6,1>,〈6,2〉，〈6,5〉}; 若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，按主教材中介绍的拓朴排序算法进行排序，试给出得到的拓朴排序的序列。

根据给定的邻接表，我们可以得到各个顶点的入度：

| 顶点 | 入度 |
| --- | --- |
| 1 | 0 |
| 2 | 2 |
| 3 | 1 |
| 4 | 2 |
| 5 | 2 |
| 6 | 3 |
| 7 | 1 |

从入度为0的顶点开始，按照拓扑排序算法，每次选择一个入度为0的顶点并将其从图中删除，直到图为空或不存在入度为0的顶点为止。在这个过程中，选择的顶点序列即为图的拓扑排序。

根据上表，入度为0的顶点有1和4。我们可以从顶点1和4开始，分别将其从图中删除。此时，入度为0的顶点有2和7。我们可以选择其中任意一个顶点，比如选择2，将其从图中删除。然后入度为0的顶点有3和7，选择其中任意一个，比如选择3，将其从图中删除。然后入度为0的顶点有5和7，选择其中任意一个，比如选择5，将其从图中删除。此时入度为0的顶点只剩下7，将其删除后，图为空，得到的拓扑排序为：

1 -> 4 -> 2 -> 3 -> 5 -> 6 -> 7