无向图G（V，E），其中V=｛a，b，c，d，e｝，E=｛(a，b)，（a，e），（a，c），（b，e），（c，f），（f，d），（e，d）｝，对该图从a开始进行深度优先遍历，得到的顶点序列有？分析一下

从a开始进行深度优先遍历，首先访问a，然后访问a的邻居节点b、e、c，其中b还有一个邻居节点e，因此再访问e，然后访问e的邻居节点d，d没有其他邻居节点，返回e，再访问b的另一个邻居节点a已经访问过了，所以访问b的另一个邻居节点e，但是e已经访问过了，返回b，再访问a的另一个邻居节点c，c的邻居节点f还没有被访问，因此访问f，f的邻居节点d已经被访问过了，返回f，再返回c，最后访问完a的所有邻居节点，遍历结束。

因此，顶点的访问序列为a -> b -> e -> d -> c -> f。

相关问题

无向图G=(V, E)，其中：V={a，b，c，d，e，f}， E={<a，b>10，<a，e>8，<a，c>3，<b，e>10，<b，f>7，<c，f>6，<f，d>5，<e，d>2}，请回答以下问题： （1）画出该无向图的示意图；（2）画出图的邻接矩阵存储结构示意图；（3）用普利姆算法构造由顶点a开始的最小生成树，写出构造过程。

（1）该无向图的示意图如下：

         10     8
    b --------- e
   / |         | \
10  | |7        |  2
 /   | |       |   \
a    | |       |    d
 \   | |6      |   /
3  \ | |       | / 5
   \ \|/       |/ /
    c --------- f
         6

（2）该无向图的邻接矩阵存储结构示意图如下：

   a  b  c  d  e  f
a  0  10 3  0  8  0
b  10 0  0  0  10 7
c  3  0  0  0  0  6
d  0  0  0  0  2  5
e  8  10 0  2  0  0
f  0  7  6  5  0  0

（3）用普利姆算法构造由顶点a开始的最小生成树，构造过程如下：

1. 选取a作为起始节点，将a加入生成树中。
2. 找出与a相连的边中权值最小的边<a, c>，将c加入生成树中。
3. 找出与已加入生成树的节点相连的边中权值最小的边，即<b, e>，将b和e加入生成树中。
4. 找出与已加入生成树的节点相连的边中权值最小的边，即<e, d>，将d加入生成树中。
5. 找出与已加入生成树的节点相连的边中权值最小的边，即<f, d>，将f加入生成树中。
6. 生成树中包含所有节点，算法结束。

构造过程中生成的最小生成树如下：

         8      
    b --------- e
          |      
10        |  2   
          |      
          d      
          |      
6         |      
    f --------- c
         3

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