資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究使用Dijkstra演算法查詢圖的直徑的Go程式
在這篇文章中，我們將編寫一個Go語言程式來查詢圖的直徑。圖的直徑是圖中任意兩個頂點之間的最大距離。有幾種演算法可以用來查詢圖的直徑，包括Dijkstra演算法、Floyd-Warshall演算法和廣度優先搜尋演算法。由於Dijkstra演算法可以找到源頂點與其他頂點之間的最短距離，我們也可以透過比較接收到的頂點的長度來使用它查詢最大距離。
語法
func len(v Type) int
len() 函式用於獲取任何引數的長度。它將一個引數作為我們希望查詢其長度的資料型別變數，並返回一個整數作為變數的長度。
演算法
步驟1 − 首先，我們需要匯入fmt和math包。然後定義edge結構體，它表示圖中帶有目標頂點和權重的邊。
步驟2 − 將priorityQueue型別定義為edge結構體的切片。
步驟3 − 定義dijkstra函式，該函式採用以二維edge結構體切片表示的圖和起始頂點作為引數，並使用Dijkstra演算法返回從起始頂點到所有其他頂點的最短距離。
步驟4 − 初始化dist切片以儲存最短距離，每個元素都設定為最大整數值。
步驟5 − 將起始頂點的距離設定為0。建立一個優先佇列pq，並將起始頂點和權重0壓入佇列。
步驟6 − 如果透過彈出頂點到達鄰居的距離小於當前到達鄰居的最短距離，則更新距離並將鄰居壓入優先佇列。
步驟7 − 返回包含到所有頂點的最短距離的dist切片。
步驟8 − 定義getDiameter函式並初始化圖中第一個頂點的start變數。
步驟9 − 使用dijkstra計算從結束頂點到所有其他頂點的最短距離。將diameter變數初始化為0。
步驟10 − 如果距離大於當前直徑且小於最大整數值，則更新直徑。返回直徑。
步驟11 − 現在，啟動main()函式並定義邊。透過傳遞邊作為引數來呼叫getDiameter()函式，並將獲得的結果儲存在一個變數中。
步驟12 − 在螢幕上列印獲得的結果
示例
在這個例子中，我們將編寫一個Go語言程式，使用Dijkstra演算法來查詢圖的直徑。Dijkstra演算法用於查詢圖中頂點之間的最短路徑。
package main
import (
"container/heap"
"fmt"
"math"
)
type edge struct {
to int
weight int
}
type priorityQueue []edge
func (pq priorityQueue) Len() int {
return len(pq)
}
func (pq priorityQueue) Less(i, j int) bool {
return pq[i].weight < pq[j].weight
}
func (pq priorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
}
func (pq *priorityQueue) Push(x interface{}) {
*pq = append(*pq, x.(edge))
}
func (pq *priorityQueue) Pop() interface{} {
old := *pq
n := len(old)
x := old[n-1]
*pq = old[0 : n-1]
return x
}
func dijkstra(graph [][]edge, start int) []int {
dist := make([]int, len(graph))
for i := range dist {
dist[i] = math.MaxInt32
}
dist[start] = 0
pq := make(priorityQueue, 0)
heap.Push(&pq, edge{to: start, weight: 0})
for pq.Len() > 0 {
node := heap.Pop(&pq).(edge)
if dist[node.to] < node.weight {
continue
}
for _, e := range graph[node.to] {
if nd := node.weight + e.weight; nd < dist[e.to] {
dist[e.to] = nd
heap.Push(&pq, edge{to: e.to, weight: nd})
}
}
}
return dist
}
func getDiameter(graph [][]edge) int {
var start int
for i := range graph {
start = i
break
}
dist := dijkstra(graph, start)
var end int
for i, d := range dist {
if d < math.MaxInt32 && dist[end] < d {
end = i
}
}
dist = dijkstra(graph, end)
var diameter int
for _, d := range dist {
if d > diameter && d < math.MaxInt32 {
diameter = d
}
}
return diameter
}
func main() {
graph := [][]edge{
{{1, 5}, {2, 3}},
{{1, 5}, {2, 1}, {3, 6}, {4, 8}},
{{1, 3}, {1, 1}, {4, 7}},
{{1, 6}, {4, 9}},
{{1, 8}, {2, 7}, {3, 9}},
}
fmt.Println("The given vertices are:", graph)
diameter := getDiameter(graph)
fmt.Println("Diameter obtained is:", diameter)
}
輸出
The given vertices are: [[{1 5} {2 3}] [{1 5} {2 1} {3 6} {4 8}] [{1 3} {1 1} {4 7}] [{1 6} {4 9}] [{1 8} {2 7} {3 9}]]
Diameter obtained is: 9
結論
在本文中，我們討論了使用Go語言中的Dijkstra演算法查詢圖直徑的方法。此方法用於獲取圖中最小的頂點長度。為了計算直徑，我們將每個頂點的距離與直徑的當前值進行比較。如果距離大於直徑，則需要更新該值，並繼續直到獲得最大距離，這實際上是圓的直徑。
231 次瀏覽
