毕业论文初稿(9)

最小生成树

后进行比较，选取值较小的元素。该元素所对应的边就是我们要寻找的边。如果是边的集合没有连通，则先将这些边的脚标取并集，然后在权矩阵分别找出该并集中每个脚标所对应行的次非零最小元，比较，取值最小的元素。这样，找到的边与前面k个非零最小元对应的k条边构成的图就是所求的最小生成树。

1.2 算法步骤

Step1：根据图的顶点数n及相应顶点间边的权值形成权矩阵A。其中主对角线元素Aii=0；若顶点i与顶点j不直接相连，Aij=0。若原图未对节点编号，则应先编号。

Step2：在权矩阵A中，按行搜索非零最小元。若某行中有几个非零最小元，则任取其一。记录各行的非零最小元及其脚标，并将权矩阵中对应的该元素赋值为0，其关于对角线对称的元素也应为0，得到新的权矩阵B（这样后面寻找行的次非零最小元就转换成寻找该行的非零最小元了）。比较找到的所有非零最小元，如果同时存在Aij、Aji，则去掉其中一个。统计此时非零最小元的个数k。

Step3：比较k与n-1的大小。若k=n-1，则由这k个元素对应的k条边构成的图即为所求最小生成树。结束。若k﹤n-1，说明这k条边构成的图没有连通，转Step4。

Step4：在剩下的边中寻找权值最小的（n-1-k）条边使k个非零