毕业论文初稿(8)

最小生成树

因为矩阵是4行4列的），只能小于等于3。

同理，在有n个顶点的带权无向连通图中，它所对应的权矩阵按行搜索到的非零最小元个数k必然小于等于n-1。

已知非零最小元的个数k，接下来判断k是否等于n-1。若k=n-1，则这k条边一定可以构成一个含有n个顶点的无回路连通图。而且这k个元素分别是权矩阵每行中值最小的，所以它们的和也最小。因此，由这k个非零最小元对应的k条边构成的图满足了n个顶点、n-1条边、权值和最小、连通且无回路的条件，此即为图G的最小生成树。

如果k﹤n-1，说明由这k条边构成的图没有连通。在图中，如果边aij（顶点i与顶点j之间的边）与amn（顶点m与顶点n之间的边）相连，那它们必然共用一个顶点，即脚标ij、mn必然有交集，否则这两条边就不连通。因此，要判断一条边或一个边的集合（这里把连通的几条边称为边的集合，一个边的集合至少包含两条边，如{a12，a13，a34}与图中其他边是否相连，只需看这条边的脚标或这个边集合中所有边的脚标的并集与图中其他边的脚标是否有交集。有交集，则说明连通；否则就没有连通。n-1条边可将n个顶点连通，所以根据n-1-k的值，可以判断还需几条边才能将k条边构成的图连通。由此也限定了我们应该找到与图中其他边未连通的边（或边的集合）的数目为n-1-k。找到未连通的边aij（或边的集合）后，下一步就应设法找到能将边aij（或边的集合）与图中其他边连接起来并且权值最小的边。也就是在权矩阵里分别找出未连通边aij的脚标i和j对应的行的次非零最小元（前面已经找过每行的非零最小元了），然