資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Go語言程式，用於查詢加權有向圖中連線所有節點的最小邊數
在本文中，我們將編寫 Go 語言程式來查詢加權有向圖中連線所有節點的最小邊數。我們將使用 Prim 演算法來執行此操作。這是一個貪婪演算法，用於查詢圖的最小生成樹。
語法
func range(variable)
可以使用 range 函式迭代任何資料型別。這可以透過首先編寫 range 關鍵字，然後編寫我們希望迭代到的資料型別來實現。
func make ([] type, size, capacity)
Go 語言的 make 函式用於構建陣列或對映；它將要形成的變數型別及其大小和容量作為引數。
func len(v Type) int
可以使用 len() 方法確定任何引數的長度。它需要一個引數——我們想要確定其長度的資料型別變數——並返回一個表示變數長度的整數值。
演算法
步驟 1 − 建立一個名為 Edge 的結構體來表示圖的邊。每條邊包含源頂點和目標頂點，以及邊的權重。
步驟 2 − 建立一個名為 minEdgesInGraph 的函式，該函式接受圖的邊和頂點數作為輸入，並返回連線所有節點所需的最小邊數。
步驟 3 − 建立一個二維距離矩陣，其中包含所有頂點之間的最大距離，對角線元素設定為 0。此矩陣表示頂點之間的距離。
步驟 4 − 遍歷輸入邊，根據需要更新距離矩陣。將每條邊的權重設定為源頂點和目標頂點之間的距離。
步驟 5 − 使用 Floyd-Warshall 演算法在距離矩陣中查詢所有頂點對之間的最短距離。在更新距離向量時考慮中間頂點。
步驟 6 − 在距離矩陣中找到最大距離。
步驟 7 − 統計圖中具有最大距離的邊數。此數字反映連線網路中所有節點所需的最小邊數。
步驟 8 − 將圖的邊和頂點數作為輸入提供給 minEdges 函式，並將結果儲存在 minEdges 變數中。
步驟 9 − 列印連線網路中所有節點所需的最小邊數。
示例
在此示例中，我們將編寫一個 Go 語言程式，使用 Prim 演算法（有助於查詢最小生成樹）來查詢加權有向圖中的最小邊數。
package main
import (
"fmt"
"math"
)
type Edge struct {
source, target, weight int
}
func minEdgesInGraph(edges []Edge, numVertices int) int {
distances := make([][]int, numVertices)
for i := range distances {
distances[i] = make([]int, numVertices)
for j := range distances[i] {
if i != j {
distances[i][j] = math.MaxInt32
}
}
}
for _, edge := range edges {
distances[edge.source][edge.target] = edge.weight
}
for k := 0; k < numVertices; k++ {
for i := 0; i < numVertices; i++ {
for j := 0; j < numVertices; j++ {
if distances[i][k]+distances[k][j] < distances[i][j] {
distances[i][j] = distances[i][k] + distances[k][j]
}
}
}
}
maxDistance := 0
for i := 0; i < numVertices; i++ {
for j := 0; j < numVertices; j++ {
if distances[i][j] > maxDistance {
maxDistance = distances[i][j]
}
}
}
count := 0
for i := 0; i < numVertices; i++ {
for j := 0; j < numVertices; j++ {
if distances[i][j] == maxDistance {
count++
}
}
}
return count
}
func main() {
edges := []Edge{
{0, 1, 4},
{0, 2, 3},
{1, 2, 1},
{1, 3, 2},
{2, 3, 4},
{2, 4, 2},
{3, 4, 3},
{3, 5, 1},
{4, 5, 5},
}
numVertices := 6
minEdges := minEdgesInGraph(edges, numVertices)
fmt.Println("Minimum number of edges in the graph:", minEdges)
}
輸出
Minimum number of edges in the graph : 15
結論
在本文中，我們已經編譯並執行了使用 Prim 演算法查詢連線所有節點的加權有向圖中最小邊數的程式。
128 次瀏覽
