Question

设无向网G的顶点集为{V0,V1，V2，V3，V4，V5},该图的邻接矩阵如下所示，试画出邻接矩阵对应的无向网，并

求最小生成树，我要做题的方法。

Answer 1

首先，由于是无向图，所以上表中的信息关于主对角线对称。这样，在做的时候，只看任意一半就可以了；
然后，开始画图。表中所有不为空的格子，表示在其所在的行列代表的顶点之前有一条权值为格子中的数字的边，举例说明，V0行V1列的值为3，即表示V0和V1之间有一条权值为3的边。
这样，处理完半张表后，无向网就画好了。
求最小生成树可以按照以下方法进行：
a.先将任意一个点加入生成树；
b.在遍历生成树中所有的点，找出一端连接树中的点，另一端连接树以外点的边中权值最小的一条，将该边以及该边连接的树外的点加入生成树；
c.重复b直到生成树包含无向图中全部的顶点。
举个例子，第一步，先把V0加进来，然后找连接V0的权值最小的边，于是找到V0－V2，加进来，再找连接V0和V2，而另一个顶点不在树中的边，于是找到V2－V1……

希望对你有帮助，图我就不画了，你自己尝试一下。

追问

那生成的无向图是唯一的吗？我自己生成了一个和答案不一样， 还有那个深度优先遍历和广度优先遍历出来的那个是不是唯一的？

追答

生成的无向图不一定唯一，但是它们是同构的；
找到的最小生成树可能不唯一，也可能不同构，因为有些顶点可能包含多条边均在某一时刻（或不同时刻）满足被添加到生成树的条件，但这个顶点只能被添加一次。