資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告