2021-04-20：手写代码：最小生成树算法之Prim。

2021-04-20：手写代码：最小生成树算法之Prim。

福大大 答案2021-04-20：

解锁点，解锁边，解锁点，解锁边，一直解锁下去。

代码用golang编写。代码如下：

package main

import (

    "fmt"

    "math"

)

func main() {

    graph := [][]int{

        {0, 11, 55},

        {math.MaxInt32, 0, 22},

        {math.MaxInt32, math.MaxInt32, 0}}

    ret := prim(graph)

    fmt.Println(ret)

}

// 请保证graph是连通图

// graph[i][j]表示点i到点j的距离，如果是系统最大值代表无路

// 返回值是最小连通图的路径之和

func prim(graph [][]int) int {

    size := len(graph)

    distances := make([]int, size)

    visit := make([]bool, size)

    visit[0] = true

    for i := 0; i < size; i++ {

        distances[i] = graph[0][i]

    }

    sum := 0

    for i := 1; i < size; i++ {

        minPath := math.MaxInt32

        minIndex := -1

        for j := 0; j < size; j++ {

            if !visit[j] && distances[j] < minPath {

                minPath = distances[j]

                minIndex = j

            }

        }

        if minIndex == -1 {

            return sum

        }

        visit[minIndex] = true

        sum += minPath

        for j := 0; j < size; j++ {

            if !visit[j] && distances[j] > graph[minIndex][j] {

                distances[j] = graph[minIndex][j]

            }

        }

    }

    return sum

}

执行结果如下：

左神java代码

2021-04-20：手写代码：最小生成树算法之Prim。的相关教程结束。