已知一个无向网的顶点集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)},其中的三元组分别表示2个邻接顶点和权值,分别写出用Prim算法和Kruskal算法在构造最小生成树时依次得到的各条最小生成边。
时间: 2023-09-25 17:11:18 浏览: 67
使用Prim算法构造最小生成树的过程如下:
1. 任选一个起点,比如选择顶点1;
2. 找到与起点相邻的最小边,将其加入最小生成树中,这里是(1,2,3);
3. 接着找到与已经加入最小生成树的点相邻的最小边,将其加入最小生成树中,这里是(1,3,5);
4. 继续找到与已经加入最小生成树的点相邻的最小边,将其加入最小生成树中,这里是(3,6,9);
5. 重复步骤4,加入边(4,6,4)、(2,5,10)、(5,6,18)、(1,4,8);
6. 最后加入边(4,7,20),得到的最小生成树的边集为{(1,2,3),(1,3,5),(3,6,9),(4,6,4),(2,5,10),(5,6,18),(1,4,8),(4,7,20)}。
使用Kruskal算法构造最小生成树的过程如下:
1. 将所有边按照权值从小到大排序,得到的顺序为(4,6,4)、(1,2,3)、(1,4,8)、(3,6,9)、(2,3,6)、(5,6,18)、(3,5,12)、(1,3,5)、(4,7,20)、(2,5,10)、(6,7,25);
2. 从权值最小的边开始,判断该边的两个端点是否在同一连通块中,如果不在,则将该边加入最小生成树中,否则舍弃该边;
3. 重复步骤2,直到最小生成树的边数等于顶点数减一,得到的最小生成树的边集为{(4,6,4),(1,2,3),(1,3,5),(3,6,9),(2,5,10),(5,6,18),(4,7,20)}。
相关问题
已知一个带权图的顶点集V和边集G分别为: V={0,1,2,3,4,5}; E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(4,5)10}, (1)画出该图并给出其邻接表表示。 (2)求出该图的最小生成树的权。
(1) 该图的邻接表表示如下:
| 顶点 | 邻接点及权值 |
| --- | --- |
| 0 | (1, 8), (2, 5), (3, 2) |
| 1 | (0, 8), (5, 6) |
| 2 | (0, 5), (3, 25), (4, 13) |
| 3 | (0, 2), (2, 25), (5, 9) |
| 4 | (2, 13), (5, 10) |
| 5 | (1, 6), (3, 9), (4, 10) |
(2) 该图的最小生成树的权为:35。
最小生成树的边依次为:(0, 3), (0, 2), (0, 1), (1, 5), (4, 5)。
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