グラフ探索の基本概念
グラフ探索の目的は以下のような課題を解決することにあります。
-
パス探索
- あるノードから別のノードへの経路を見つける
-
到達可能性判定
- 特定のノードが別のノードに到達可能か確認する
-
最短経路探索
- 2つのノード間の最短経路を発見する
-
連結性の確認
- グラフ全体が一つの塊（連結グラフ）であるか調べる
主要なグラフ探索アルゴリズム
1. 深さ優先探索 (Depth First Search, DFS)
DFSはスタック（または再帰）を用いてグラフを探索します。探索は可能な限り深く進み、行き止まりに到達した場合は引き返して次の道を探します。
Goサンプルコード
package main
import "fmt"
func dfs(graph map[int][]int, node int, visited map[int]bool) {
// 現在のノードを訪問済みとする
visited[node] = true
fmt.Println(node)
// 隣接ノードを再帰的に探索
for _, neighbor := range graph[node] {
if !visited[neighbor] {
dfs(graph, neighbor, visited)
}
}
}
func main() {
// グラフの表現（隣接リスト）
graph := map[int][]int{
0: {1, 2},
1: {0, 3, 4},
2: {0, 4},
3: {1},
4: {1, 2},
}
// 訪問状態を保持するマップ
visited := make(map[int]bool)
dfs(graph, 0, visited)
}
0
1
3
4
2
2. 幅優先探索 (Breadth First Search, BFS)
BFSはキューを用いてグラフを探索します。探索は現在の階層をすべて探索してから次の階層に進みます。
Goサンプルコード
package main
import "fmt"
func bfs(graph map[int][]int, start int) {
// 訪問状態を保持するマップ
visited := make(map[int]bool)
// キューに開始ノードを追加
queue := []int{start}
visited[start] = true
for len(queue) > 0 {
// キューから現在のノードを取得
current := queue[0]
queue = queue[1:]
fmt.Println(current)
// 隣接ノードを探索
for _, neighbor := range graph[current] {
if !visited[neighbor] {
visited[neighbor] = true
queue = append(queue, neighbor)
}
}
}
}
func main() {
// グラフの表現（隣接リスト）
graph := map[int][]int{
0: {1, 2, 5},
1: {0, 3, 4},
2: {0, 4},
3: {1},
4: {1, 2},
5: {0, 6},
6: {5, 7},
7: {6},
}
bfs(graph, 0)
}
0
1
2
5
3
4
6
7
3. ダイクストラ法
ダイクストラ法は、(負ではない)重みを持つグラフにおける最短経路を探索するアルゴリズムです。
Goサンプルコード
package main
import (
"container/heap"
"fmt"
"math"
)
type Edge struct {
to string
weight int
}
type Node struct {
id string
dist int
}
// PriorityQueue implements heap.Interface
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{}) {
*pq = append(*pq, x.(Node))
}
func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
*pq = old[0 : n-1]
return item
}
func dijkstra(graph map[string][]Edge, start string) map[string]int {
dist := make(map[string]int)
for node := range graph {
dist[node] = math.MaxInt
}
dist[start] = 0
pq := &PriorityQueue{}
heap.Push(pq, Node{start, 0})
for pq.Len() > 0 {
current := heap.Pop(pq).(Node)
for _, edge := range graph[current.id] {
newDist := dist[current.id] + edge.weight
if newDist < dist[edge.to] {
dist[edge.to] = newDist
heap.Push(pq, Node{edge.to, newDist})
}
}
}
return dist
}
func main() {
// グラフの表現（隣接リスト）
graph := map[string][]Edge{
"A": {{"B", 1}, {"C", 4}},
"B": {{"A", 1}, {"C", 2}, {"D", 5}},
"C": {{"A", 4}, {"B", 2}, {"D", 1}},
"D": {{"B", 5}, {"C", 1}},
}
start := "A"
distances := dijkstra(graph, start)
for node, dist := range distances {
fmt.Printf("Node %s: Distance from start = %d\n", node, dist)
}
}
Node A: Distance from start = 0
Node B: Distance from start = 1
Node C: Distance from start = 3
Node D: Distance from start = 4