グラフ探索の基本概念

グラフ探索の目的は以下のような課題を解決することにあります。

パス探索
- あるノードから別のノードへの経路を見つける
到達可能性判定
- 特定のノードが別のノードに到達可能か確認する
最短経路探索
- 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)
}

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)
}

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