图的最小生成树

prim算法

let maxvex = 20
let maxedge = 20
let infinity = 65535
struct MGraph{
    var arc:[[Int]]
    var numVertexes:Int
    var numEdges:Int
    init() {
        self.arc = [[Int]](repeating: [Int](repeating: 0, count: maxvex), count: maxvex)
        self.numVertexes = 9
        self.numEdges=15
        for i in 0..<self.numVertexes {
            for j in 0..<self.numVertexes {
                if (i == j) {
                    self.arc[i][j] = 0
                } else{
                    self.arc[i][j] = infinity
                    self.arc[j][i] = self.arc[i][j]
                }
            }
        }
        self.arc[0][1] = 10
        self.arc[0][5] = 11
        self.arc[1][2] = 18
        self.arc[1][8] = 12
        self.arc[1][6] = 16
        self.arc[2][8] = 8
        self.arc[2][3] = 22
        self.arc[3][8] = 21
        self.arc[3][7] = 16
        self.arc[3][4] = 20
        self.arc[4][7] = 7
        self.arc[4][5] = 26
        self.arc[5][6] = 17
        self.arc[6][7] = 19
        for i in 0..<self.numVertexes {
            for j in 0..<self.numVertexes {
                self.arc[j][i] = self.arc[i][j]
            }
        }
    }
}

func miniSpanTree_Prim(_ graph:MGraph){
    var min:Int
    var k:Int
    var sum:Int = 0
    var adjvex = [Int](repeating: 0, count: maxvex)
    var lowcost = [Int](repeating: 0, count: maxvex)
    lowcost[0] = 0
    adjvex[0] = 0
    for i in 1..<graph.numVertexes {
        lowcost[i] = graph.arc[0][i]//默认从第0个点开始，lowcost此时存储的是与第0个点的所有连接点的权值，如果不连接则为 infinity即无穷大
        adjvex[i] = 0//此时数组adjvex默认存入0点表示开始了
    }
    for _ in 1..<graph.numVertexes {
        min = infinity
        k = 0
        for j in 1..<graph.numVertexes{
            if (lowcost[j] != 0 && lowcost[j] < min) {//找到目前lowcost权值数组中权值最小的那个点
                min = lowcost[j]
                k = j
            }
        }
        sum = sum + graph.arc[adjvex[k]][k]//计算sum
        lowcost[k] = 0;//为0则表示该点已经被计算过了，接下来不参与剩下的计算
        for j in 1..<graph.numVertexes {//找到与顶点k相连的最小权值
            if (lowcost[j] != 0 && graph.arc[k][j] < lowcost[j]) {//将k与j之间权值与lowcost中j点的权值对比（即k至1,2,3,4,5,6,7,8点的权值与 lowcost存的关于1,2,3,4,5,6,7,8的权值对比），k与j的距离小于j目前存的权值，说明kj距离比目前存的权值合适
                lowcost[j] = graph.arc[k][j] //记住j的权重（即将1,2,3,4,5,6,7,8点的权值都更新）
                adjvex[j] = k//数组adjvex记住j的连接的顶点(即记住与1,2,3,4,5,6,7,8点连接的点)
            }
        }
    }
    print("sum = %d\n", sum)
}

func main(){
    let graph = MGraph()
    miniSpanTree_Prim(graph)
    
}