问答题
用Kruskal算法求下图中的一棵最小生成树。要求写出详细过程，并画出该最小生成树。
用Kruskal算法求下图中的一棵最小生成树。要求写出详细过程，并画出该最小生成树。
【参考答案】
解：根据Kruskal算法，
①取权为1的边e 1 =(v 1 ，v 2 )；②取权为3的边e 2 =(v 2 ，v 3 )；
③取权为4的边e 3 =(v 3 ，v 4 )；④取权为4的边e 4 =(v 3 ，v 5 )；
⑤取权为7的边e 5 =(v 5 ，v 6 )；
最小生成树如下图所示。
解：根据Kruskal算法，
①取权为1的边e 1 =(v 1 ，v 2 )；②取权为3的边e 2 =(v 2 ，v 3 )；
③取权为4的边e 3 =(v 3 ，v 4 )；④取权为4的边e 4 =(v 3 ，v 5 )；
⑤取权为7的边e 5 =(v 5 ，v 6 )；
最小生成树如下图所示。