Question

关于数据结构的深度优先遍历和广度优先遍历以及最小生成树 第四大题的第一题

• 你的回答被采纳后将获得：
• 系统奖励15（财富值+成长值）+难题奖励30（财富值+成长值）

Answer 1

首先看一下深度优先和广度优先怎么遍历：
深度优先遍历从某个顶点出发，首先访问这个顶点，然后找出刚访问这个结点的第一个未被访问的邻结点，然后再以此邻结点为顶点，继续找它的下一个新的顶点进行访问，重复此步骤，直到所有结点都被访问完为止。
广度优先遍历从某个顶点出发，首先访问这个顶点，然后找出这个结点的所有未被访问的邻接点，访问完后再访问这些结点中第一个邻接点的所有结点，重复此方法，直到所有结点都被访问完为止。
在看题目，其要求按顺时针方向：
深度优先序列：V1 V2 V3 V5 V4
广度优先序列：V1 V2 V4 V3 V5
最小生成树，有两种方法，prim和kruskal算法。
这题最小生成树如下：
[(V4,V5),(V1,V4),(V2,V4),(V5,V3)],其中（V4,V5）表示V4和V5点之间连线。如下图类似（这里简单表示一下）。
V1 V2 V3
\ / /
V4----V5