使用Dijkstra算法找到最小生成树的Golang程序

本文将编写一个Go语言程序来查找树的最小生成树。最小生成树（MST）是一棵树，它用最少的边连接了未定向、加权图中的所有节点。有几种算法可以找到图的最小生成树，例如Dijkastra算法、prim算法和kruskal算法。

什么是Dijstra算法？

Dijkstra算法是一种算法，它在加权图（边权值非负）中找到源顶点和所有其他顶点之间的最短路径。它通过维护一组已访问的节点和一组未访问的节点，并跟踪源顶点到图中每个顶点的最小距离来工作。

算法

• 步骤1 - 首先，我们需要导入fmt和math包。然后定义一个结构节点。初始化距离和访问数组。

• 步骤2 - 将源点的距离设置为0并将其推入优先级队列中。

• 步骤3 - 当优先级队列不为空时，提取最小距离的顶点。

• 步骤4 - 将提取的顶点标记为已访问，对于它的每个邻居，如果找到更短的路径，则更新它们的距离。

• 步骤5 - 如果邻居尚未访问，则将每个更新的邻居推入优先级队列中。返回最小生成树。

• 步骤6 - 现在，创建main()函数。在main()函数内初始化图节点并将其打印到屏幕上。

• 步骤7 - 现在，通过将上述节点作为参数传递给findMst()函数并将结果存储在变量中来调用findMst()函数。

• 步骤8 - 进一步，在屏幕上打印结果。

示例1

在本例中，我们将讨论使用优先级队列实现Dijkstra算法的方法。该方法的基本思想是跟踪源节点到图中每个节点的最小距离。我们还将跟踪源节点到每个节点的最短路径中的前一个节点。

package main

import (
   "container/heap"
   "fmt"
   "math"
)

type Node struct {
   id   int
   dist int
}

type PriorityQueue []*Node

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
   return pq[i].dist < pq[j].dist
}

func (pq PriorityQueue) Swap(i, j int) {
   pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
   node := x.(*Node)
   *pq = append(*pq, node)
}

func (pq *PriorityQueue) Pop() interface{} {
   old := *pq
   n := len(old)
   node := old[n-1]
   *pq = old[0 : n-1]
   return node
}

func findMST(graph [][]int, source int) [][]int {
   n := len(graph)
   dist := make([]int, n)
   prev := make([]int, n)
   visited := make([]bool, n)

   for i := 0; i < n; i++ {
      dist[i] = math.MaxInt32
   }

   dist[source] = 0
   pq := &PriorityQueue{}
   heap.Init(pq)
   heap.Push(pq, &Node{id: source, dist: 0})

   for pq.Len() > 0 {
      node := heap.Pop(pq).(*Node)
      id := node.id

      if visited[id] {
         continue
      }

      visited[id] = true

      for j := 0; j < n; j++ {
         if graph[id][j] != 0 && !visited[j] {
            alt := dist[id] + graph[id][j]
            if alt < dist[j] {
               dist[j] = alt
               prev[j] = id
               heap.Push(pq, &Node{id: j, dist: alt})
            }
         }
      }
   }

   mst := make([][]int, n)

   for i := 0; i < n; i++ {
      mst[i] = make([]int, n)
   }

   for i := 0; i < n; i++ {
      if prev[i] != i {
         mst[prev[i]][i] = graph[prev[i]][i]
         mst[i][prev[i]] = graph[prev[i]][i]
      }
   }
   return mst
}

func main() {
   graph := [][]int{
      {0, 2, 0, 6, 0},
      {2, 0, 3, 8, 5},
      {0, 3, 0, 0, 7},
      {6, 8, 0, 0, 9},
      {0, 5, 7, 9, 0},
   }
   fmt.Println("给出的节点是:", graph)
   mst := findMST(graph, 0)
   fmt.Println()
   fmt.Println("最小生成树:")
   for _, row := range mst {
      fmt.Println(row)
   }
}

输出

给出的节点是: [[0 2 0 6 0] [2 0 3 8 5] [0 3 0 0 7] [6 8 0 0 9] [0 5 7 9 0]]

最小生成树:
[0 2 0 6 0]
[2 0 3 0 5]
[0 3 0 0 0]
[6 0 0 0 0]
[0 5 0 0 0]

示例2

在第二个示例中，我们将讨论使用堆实现Dijkstra算法的方法。该方法的基本思想与第一种方法类似，但是我们将使用堆来按其距离源节点的顺序存储节点。

package main

import (
   "fmt"
   "math"
)

type Node struct {
   id   int
   dist int
}

type Heap []*Node

func (h Heap) Len() int           { return len(h) }
func (h Heap) Less(i, j int) bool { return h[i].dist < h[j].dist }
func (h Heap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *Heap) Push(x interface{}) {
   node := x.(*Node)
   *h = append(*h, node)
}

func (h *Heap) Pop() interface{} {
   old := *h
   n := len(old)
   node := old[n-1]
   *h = old[0 : n-1]
   return node
}

func findMST(graph [][]int, source int) [][]int {
   n := len(graph)
   dist := make([]int, n)
   prev := make([]int, n)
   visited := make([]bool, n)

   for i := 0; i < n; i++ {
      dist[i] = math.MaxInt32
   }

   dist[source] = 0
   heap := &Heap{}
   heap.Push(&Node{id: source, dist: 0})

   for heap.Len() > 0 {
      node := heap.Pop().(*Node)
      id := node.id

      if visited[id] {
         continue
      }

      visited[id] = true

      for j := 0; j < n; j++ {
         if graph[id][j] != 0 && !visited[j] {
            alt := dist[id] + graph[id][j]

            if alt < dist[j] {
               dist[j] = alt
               prev[j] = id
               heap.Push(&Node{id: j, dist: alt})
            }
         }
      }
   }

   mst := make([][]int, n)

   for i := 0; i < n; i++ {
      mst[i] = make([]int, n)
   }

   for i := 0; i < n; i++ {
      if prev[i] != i {
         mst[prev[i]][i] = graph[prev[i]][i]
         mst[i][prev[i]] = graph[prev[i]][i]
      }
   }
   return mst
}

func main() {
   // Example graph
   graph := [][]int{
      {0, 2, 0, 6, 0},
      {2, 0, 3, 8, 5},
      {0, 3, 0, 0, 7},
      {6, 8, 0, 0, 9},
      {0, 5, 7, 9, 0},
   }

   // Find minimum spanning tree
   mst := findMST(graph, 0)
   fmt.Println("给定图的节点是：", mst)
   fmt.Println()

   // Print minimum spanning tree
   fmt.Println("最小生成树是：")
   for _, row := range mst {
      fmt.Println(row)
   }
}

输出

给定图的节点是： [[0 2 0 6 0] [2 0 0 0 0] [0 0 0 0 7] [6 0 0 0 9] [0 0 7 9 0]]

最小生成树是：
[0 2 0 6 0]
[2 0 0 0 0]
[0 0 0 0 7]
[6 0 0 0 9]
[0 0 7 9 0]

结论

我们讨论了三种方法来实现Dijkstra算法以找到图的最小生成树。所有这些方法都是高效的，并且具有类似的时间复杂度，但是使用优先队列或堆可以比使用数组更有效。方法的选择取决于手头问题的具体要求。