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

相关问题

已知一个无向图的顶点集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加入到最小生成树中。
2. 计算A到它的相邻顶点的边的权重，选择权重最小的那条边，即(A,E)，将E加入到最小生成树中。
3. 计算A和E相邻的顶点的边的权重，选择权重最小的那条边，即(A,D)，将D加入到最小生成树中。
4. 计算A、E和D相邻的顶点的边的权重，选择权重最小的那条边，即(D,B)，将B加入到最小生成树中。
5. 计算A、E、D和B相邻的顶点的边的权重，选择权重最小的那条边，即(B,C)，将C加入到最小生成树中。
6. 由于所有的顶点都已经加入到最小生成树中，算法结束。

最终的最小生成树为：{(A,E), (A,D), (D,B), (B,C)}，其权重为9+3+1+7=20。

已知一个图的顶点集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