数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用Dijkstra算法查找最小生成树的Go语言程序
在本文中，我们将编写一个Go语言程序来查找树的最小生成树。最小生成树 (MST) 是一棵树，它以尽可能少的边连接无向加权图中的所有节点。有几种算法可以找到图的最小生成树，例如Dijkstra算法、Prim算法和Kruskal算法。
什么是Dijkstra算法？
Dijkstra算法是一种算法，它可以在具有非负边权重的加权图中找到源顶点和所有其他顶点之间的最短路径。它的工作原理是维护一组已访问顶点和一组未访问顶点，并跟踪从源顶点到图中每个顶点的最小距离。
算法
步骤1 − 首先，我们需要导入fmt和math包。然后定义一个结构体node。初始化距离和已访问数组。
步骤2 − 将源顶点的距离设置为0，并将其推入优先队列。
步骤3 − 当优先队列不为空时，从队列中提取距离最小的顶点。
步骤4 − 将提取的顶点标记为已访问，对于其每个邻居，如果找到更短的路径，则更新它们的距离。
步骤5 − 如果邻居尚未访问，则将其推入优先队列。返回最小生成树。
步骤6 − 现在，创建main()函数。在main()中初始化图的节点，并在屏幕上打印它们。
步骤7 − 现在，通过传递上述节点作为参数来调用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]
结论
我们讨论了三种在Golang中实现Dijkstra算法以查找图的最小生成树的方法。所有这些方法都是高效的，并且具有相似的时空复杂度，但是使用优先队列或堆可能比使用数组更有效率。方法的选择取决于手头问题的具体要求。
更新于：2023年4月5日
475 次浏览
广告