資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Go語言程式查詢圖中所有路徑
本文我們將學習如何使用Go語言中的深度優先搜尋演算法和廣度優先搜尋方法來查詢圖中的所有路徑。在圖中，節點由實體表示，邊表示這些實體之間的關係。查詢圖中的所有路徑是圖論中的一個常見任務，可用於各種應用。
演算法
步驟1 − 首先，我們需要匯入fmt包。
步驟2 − 然後建立不同的結構體和函式，併為其定義屬性。
步驟3 − 現在，建立main()函式。在main()函式內部初始化節點併為其賦值。
步驟4 − 接下來，透過將這些節點作為引數傳遞給graph結構體來建立邊。
步驟5 − 現在，透過將所需的節點作為引數傳遞給AllPaths()函式來呼叫它，並將獲得的結果儲存在一個變數中。
步驟6 − 使用fmt.Println()函式在螢幕上列印結果。
示例1
在這個例子中，我們將編寫一個Go語言程式，使用深度優先搜尋來查詢圖中的所有路徑。深度優先搜尋(DFS)演算法是用於遍歷和搜尋圖的經典演算法。
package main
import "fmt"
type Node struct {
name string
}
type Edge struct {
source *Node
dest *Node
}
type Graph struct {
nodes []*Node
edges []*Edge
}
func (g *Graph) AddNode(n *Node) {
g.nodes = append(g.nodes, n)
}
func (g *Graph) AddEdge(s *Node, d *Node) {
e := &Edge{source: s, dest: d}
g.edges = append(g.edges, e)
}
func (g *Graph) DFS(s *Node, d *Node, visited map[*Node]bool, path []string, paths *[][]string) {
visited[s] = true
path = append(path, s.name)
if s == d {
*paths = append(*paths, path)
} else {
for _, e := range g.edges {
if e.source == s && !visited[e.dest] {
g.DFS(e.dest, d, visited, path, paths)
}
}
}
delete(visited, s)
path = path[:len(path)-1]
}
func (g *Graph) AllPaths(s *Node, d *Node) [][]string {
visited := make(map[*Node]bool)
paths := [][]string{}
path := []string{}
g.DFS(s, d, visited, path, &paths)
return paths
}
func main() {
a := &Node{name: "A"}
b := &Node{name: "B"}
c := &Node{name: "C"}
d := &Node{name: "D"}
g := &Graph{}
g.AddNode(a)
g.AddNode(b)
g.AddNode(c)
g.AddNode(d)
g.AddEdge(a, b)
g.AddEdge(b, c)
g.AddEdge(a, c)
g.AddEdge(c, d)
paths := g.AllPaths(a, d)
fmt.Println("The required paths in a graph are:", paths)
}
輸出
The required paths in a graph are: [[A B C D] [A C D]]
示例2
在這個例子中，我們將編寫一個Go語言程式，使用廣度優先搜尋方法來查詢圖中的所有路徑。
package main
import "fmt"
type Node struct {
name string
}
type Edge struct {
source *Node
dest *Node
}
type Graph struct {
nodes []*Node
edges []*Edge
}
func (g *Graph) AddNode(n *Node) {
g.nodes = append(g.nodes, n)
}
func (g *Graph) AddEdge(s *Node, d *Node) {
e := &Edge{source: s, dest: d}
g.edges = append(g.edges, e)
}
func (g *Graph) BFS(s *Node, d *Node) [][]string {
visited := make(map[*Node]bool)
queue := [][]*Node{{s}}
paths := [][]string{}
for len(queue) > 0 {
path := queue[0]
queue = queue[1:]
node := path[len(path)-1]
if node == d {
var pathStr []string
for _, n := range path {
pathStr = append(pathStr, n.name)
}
paths = append(paths, pathStr)
}
for _, e := range g.edges {
if e.source == node && !visited[e.dest] {
newPath := append(path, e.dest)
queue = append(queue, newPath)
visited[e.dest] = true
}
}
}
return paths
}
func main() {
a := &Node{name: "A"}
b := &Node{name: "B"}
c := &Node{name: "C"}
d := &Node{name: "D"}
g := &Graph{}
g.AddNode(a)
g.AddNode(b)
g.AddNode(c)
g.AddNode(d)
g.AddEdge(a, b)
g.AddEdge(b, c)
g.AddEdge(a, c)
g.AddEdge(c, d)
paths := g.BFS(a, d)
fmt.Println("The required paths are:", paths)
}
輸出
The required paths are: [[A C D]]
結論
我們已經成功地編譯並執行了一個Go語言程式來查詢圖中的所有路徑，並附帶了示例。這用於網路路由、社交網路分析和推薦系統等應用。我們展示了兩種方法，即廣度優先搜尋和深度優先搜尋來實現此結果。
更新於：2023年4月5日
664 次瀏覽
廣告