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〉}; 若存储它采用邻接表,并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的,按主教材中介绍的拓朴排序算法进行排序,试给出得到的拓朴排序的序列。
时间: 2024-04-01 18:37:27 浏览: 21
根据给定的邻接表,我们可以得到各个顶点的入度:
| 顶点 | 入度 |
| --- | --- |
| 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
相关问题
已知一个无向图的顶点集V和边集E分别为:V={A,B,C,D,E};E={(A,B)9,(A,D)3,(A,E)2,(B.C)1,(C,D)7,(D,E)4}。请回答以下问题: (1)画出该图的逻辑结构图示; (2)用普里姆算法求出该图从A顶点开始的最小生成树,并写出构造过程。
(1) 该图的逻辑结构图示如下:
```
9 1
A ------ B ------ C
| \ | |
3 | \2 |7 |
| \ | |
D ------ E ------
4
```
(2) 该图从顶点A开始的最小生成树构造过程如下:
1. 以A为起点,将A加入最小生成树中,标记A为已访问。
2. 将与A相邻的未访问顶点B、D、E的权值加入小根堆中。
3. 弹出小根堆中权值最小的边(A,E),将E加入最小生成树中,标记E为已访问。
4. 将与E相邻的未访问顶点D、F的权值加入小根堆中。
5. 弹出小根堆中权值最小的边(E,A),由于A已访问,直接舍弃。
6. 弹出小根堆中权值最小的边(E,D),将D加入最小生成树中,标记D为已访问。
7. 将与D相邻的未访问顶点C、E、G的权值加入小根堆中。
8. 弹出小根堆中权值最小的边(D,E),由于E已访问,直接舍弃。
9. 弹出小根堆中权值最小的边(D,C),将C加入最小生成树中,标记C为已访问。
10. 将与C相邻的未访问顶点B、D、F的权值加入小根堆中。
11. 弹出小根堆中权值最小的边(C,B),将B加入最小生成树中,标记B为已访问。
12. 将与B相邻的未访问顶点D、E的权值加入小根堆中。
13. 弹出小根堆中权值最小的边(B,C),由于C已访问,直接舍弃。
14. 弹出小根堆中权值最小的边(B,E),由于E已访问,直接舍弃。
15. 完成,最小生成树为:A -- E(2) -- D(4) -- C(1) -- B(9)。
已知一个带权图的顶点集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)。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)