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

在本文中，我们将编写一个Go语言程序来找到树的最小生成。最小生成树（MST）是一棵连接无向加权图中所有节点的树，且边数最小。有几种算法可以找到图的最小生成树，如Dijkstra算法、Prim算法和Kruskal算法。

Dijkstra算法是什么

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

步骤

步骤1 - 首先，我们需要导入fmt和math包。然后定义一个struct node。初始化距离和visited数组。
步骤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("The given nodes are:", graph)
   mst := findMST(graph, 0)
   fmt.Println()
   fmt.Println("Minimum Spanning Tree:")
   for _, row := range mst {
      fmt.Println(row)
   }
}

输出

The given nodes are: [[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]]

Minimum Spanning Tree:
[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("The given nodes of the graph are:", mst)
   fmt.Println()

   // Print minimum spanning tree
   fmt.Println("Minimum spanning tree is:")
   for _, row := range mst {
      fmt.Println(row)
   }
}

输出

The given nodes of the graph are: [[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]]

Minimum spanning tree is:
[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]