はじめに (対象読者・この記事でわかること)

この記事は、Go言語の基本的な文法を理解している方を対象にしています。特に、アルゴリズムの実装経験がある方や、Go言語でグラフアルゴリズムを実装してみたい方に向けています。

この記事を読むことで、Go言語で幅優先探索を実装する際に遭遇する可能性のある奇妙な挙動とその原因、そして適切な解決策を理解できます。また、Go言語のチャネルやゴルーチンを活用した並行処理の基本的な考え方についても学べます。

前提知識

この記事を読み進める上で、以下の知識があるとスムーズです。 前提となる知識1: Go言語の基本的な文法 前提となる知識2: アルゴリズムの基本的な知識、特に幅優先探索

Go言語で幅優先探索を実装する際の不思議な挙動

幅優先探索（Breadth-First Search、BFS）は、グラフや木構造を探索するための基本的なアルゴリズムの一つです。このアルゴリズムは、探索を開始ノードから近いノードから順に広がっていくため、最短経路の探索などに広く利用されています。

Go言語は、その並行処理能力の高さから、アルゴリズムの実装にも適しています。特に、チャネルやゴルーチンを活用することで、並列処理を簡単に実装できます。しかし、これらの機能を活用する際には、Go言語特有の挙動を理解しておく必要があります。

今回の記事では、Go言語で幅優先探索を実装する際に遭遇した奇妙な挙動とその原因、そして解決策について解説します。この問題は、Go言語のチャネルとゴルーチンの動作特性に起因するものであり、理解しておくと他の並行処理の実装でも役立つ知識となります。

具体的な手順や実装方法

ステップ1：幅優先探索の基本的な実装

まずは、Go言語で幅優先探索を基本的な方法で実装してみましょう。以下に、グラフを隣接リストで表現し、幅優先探索を行うコードの例を示します。

Go

package main

import (
    "fmt"
    "container/list"
)

// グラフの頂点を表す構造体
type Vertex struct {
    id       int
    visited  bool
    distance int
}

// グラフを表す構造体
type Graph struct {
    vertices []*Vertex
    adjList  map[int][]int
}

// グラフに頂点を追加
func (g *Graph) AddVertex(id int) {
    g.vertices = append(g.vertices, &Vertex{id: id, visited: false, distance: -1})
    g.adjList[id] = []int{}
}

// グラフに辺を追加
func (g *Graph) AddEdge(from, to int) {
    g.adjList[from] = append(g.adjList[from], to)
    g.adjList[to] = append(g.adjList[to], from)
}

// 幅優先探索の実装
func (g *Graph) BFS(start int) {
    queue := list.New()

    // 開始頂点をキューに追加
    for _, v := range g.vertices {
        if v.id == start {
            v.visited = true
            v.distance = 0
            queue.PushBack(v)
            break
        }
    }

    // キューが空になるまで探索を続ける
    for queue.Len() > 0 {
        // キューから頂点を取り出す
        current := queue.Remove(queue.Front()).(*Vertex)
        fmt.Printf("頂点 %d (距離: %d) を探索\n", current.id, current.distance)

        // 隣接頂点を探索
        for _, neighborID := range g.adjList[current.id] {
            for _, v := range g.vertices {
                if v.id == neighborID && !v.visited {
                    v.visited = true
                    v.distance = current.distance + 1
                    queue.PushBack(v)
                }
            }
        }
    }
}

func main() {
    // グラフの作成
    g := Graph{
        vertices: []*Vertex{},
        adjList:  make(map[int][]int),
    }

    // 頂点の追加
    for i := 1; i <= 6; i++ {
        g.AddVertex(i)
    }

    // 辺の追加
    g.AddEdge(1, 2)
    g.AddEdge(1, 3)
    g.AddEdge(2, 4)
    g.AddEdge(2, 5)
    g.AddEdge(3, 6)

    // 幅優先探索の実行
    fmt.Println("幅優先探索の開始:")
    g.BFS(1)
}

このコードでは、container/listパッケージを使用してキューを実装しています。Vertex構造体には頂点のID、訪問済みフラグ、開始頂点からの距離を保持しています。Graph構造体には頂点のスライスと隣接リストを保持しています。

BFSメソッドでは、まず開始頂点をキューに追加し、その後キューが空になるまで探索を続けます。キューから頂点を取り出し、その隣接頂点を探索して未訪問の頂点があればキューに追加します。

ステップ2：ゴルーチンとチャネルを活用した並行処理の実装

次に、Go言語の特徴であるゴルーチンとチャネルを活用した並行処理の実装を試みます。以下に、ゴルーチンとチャネルを使用した幅優先探索の実装例を示します。

Go

package main

import (
    "fmt"
    "sync"
)

// グラフの頂点を表す構造体
type Vertex struct {
    id       int
    visited  bool
    distance int
}

// グラフを表す構造体
type Graph struct {
    vertices []*Vertex
    adjList  map[int][]int
    mu       sync.Mutex
}

// グラフに頂点を追加
func (g *Graph) AddVertex(id int) {
    g.vertices = append(g.vertices, &Vertex{id: id, visited: false, distance: -1})
    g.adjList[id] = []int{}
}

// グラフに辺を追加
func (g *Graph) AddEdge(from, to int) {
    g.adjList[from] = append(g.adjList[from], to)
    g.adjList[to] = append(g.adjList[to], from)
}

// 幅優先探索の実装（ゴルーチンとチャネルを使用）
func (g *Graph) ConcurrentBFS(start int) {
    queue := make(chan *Vertex, 100)
    var wg sync.WaitGroup

    // 開始頂点をキューに追加
    for _, v := range g.vertices {
        if v.id == start {
            v.visited = true
            v.distance = 0
            queue <- v
            wg.Add(1)
            go g.processVertex(queue, &wg)
            break
        }
    }

    // ゴルーチンの終了を待つ
    wg.Wait()
    close(queue)
}

// 頂点を処理するゴルーチン
func (g *Graph) processVertex(queue chan *Vertex, wg *sync.WaitGroup) {
    defer wg.Done()

    for current := range queue {
        fmt.Printf("頂点 %d (距離: %d) を探索\n", current.id, current.distance)

        // 隣接頂点を探索
        for _, neighborID := range g.adjList[current.id] {
            for _, v := range g.vertices {
                if v.id == neighborID && !v.visited {
                    g.mu.Lock()
                    if !v.visited {
                        v.visited = true
                        v.distance = current.distance + 1
                        queue <- v
                        wg.Add(1)
                    }
                    g.mu.Unlock()
                }
            }
        }
    }
}

func main() {
    // グラフの作成
    g := Graph{
        vertices: []*Vertex{},
        adjList:  make(map[int][]int),
    }

    // 頂点の追加
    for i := 1; i <= 6; i++ {
        g.AddVertex(i)
    }

    // 辺の追加
    g.AddEdge(1, 2)
    g.AddEdge(1, 3)
    g.AddEdge(2, 4)
    g.AddEdge(2, 5)
    g.AddEdge(3, 6)

    // 幅優先探索の実行
    fmt.Println("並行処理による幅優先探索の開始:")
    g.ConcurrentBFS(1)
}

このコードでは、syncパッケージを使用してミューテックスとWaitGroupを実装しています。チャネルqueueを使用してゴルーチン間で頂点を共有し、processVertex関数をゴルーチンとして実行しています。

ハマった点やエラー解決

この並行処理の実装では、いくつかの問題が発生しました。最も顕著な問題は、探索が正しく完了しないことでした。具体的には、一部の頂点が探索されない、または探索順序がおかしいといった現象が発生しました。

この問題の原因は、Go言語のチャネルの動作特性と、ゴルーチン間でのデータ共有の方法にありました。特に、以下の2つの問題が原因でした。

  1. チャネルのバッファサイズ不足: 初期の実装では、チャネルのバッファサイズを10に設定していました。しかし、グラフのサイズが大きくなると、チャネルが満杯になり、ゴルーチンがブロックされてしまいました。

  2. 競合状態: 複数のゴルーチンが同時に頂点の訪問済みフラグをチェック・更新するため、競合状態が発生していました。これにより、一部の頂点が複数のゴルーチンによって同時に処理される可能性がありました。

解決策

これらの問題を解決するために、以下の対策を取りました。

  1. チャネルのバッファサイズの調整: チャネルのバッファサイズをグラフの頂点数以上に設定することで、チャネルが満杯になるのを防ぎました。具体的には、バッファサイズを100に設定しました。

  2. ミューテックスの使用: sync.Mutexを使用して、頂点の訪問済みフラグのチェックと更新をアトミックに行うようにしました。これにより、競合状態を防ぎました。

  3. WaitGroupの適切な使用: sync.WaitGroupを使用して、すべてのゴルーチンが終了するのを正しく待つようにしました。特に、新しい頂点がキューに追加されるたびに、対応するゴルーチンが終了するまで待つようにしました。

これらの対策を取り入れた結果、並行処理による幅優先探索が正しく動作するようになりました。以下に、修正後の完全なコードを示します。

Go

package main

import (
    "fmt"
    "sync"
)

// グラフの頂点を表す構造体
type Vertex struct {
    id       int
    visited  bool
    distance int
}

// グラフを表す構造体
type Graph struct {
    vertices []*Vertex
    adjList  map[int][]int
    mu       sync.Mutex
}

// グラフに頂点を追加
func (g *Graph) AddVertex(id int) {
    g.vertices = append(g.vertices, &Vertex{id: id, visited: false, distance: -1})
    g.adjList[id] = []int{}
}

// グラフに辺を追加
func (g *Graph) AddEdge(from, to int) {
    g.adjList[from] = append(g.adjList[from], to)
    g.adjList[to] = append(g.adjList[to], from)
}

// 幅優先探索の実装（ゴルーチンとチャネルを使用）
func (g *Graph) ConcurrentBFS(start int) {
    queue := make(chan *Vertex, 100) // バッファサイズをグラフのサイズ以上に設定
    var wg sync.WaitGroup

    // 開始頂点をキューに追加
    for _, v := range g.vertices {
        if v.id == start {
            g.mu.Lock()
            v.visited = true
            v.distance = 0
            g.mu.Unlock()
            queue <- v
            wg.Add(1)
            go g.processVertex(queue, &wg)
            break
        }
    }

    // ゴルーチンの終了を待つ
    wg.Wait()
    close(queue)
}

// 頂点を処理するゴルーチン
func (g *Graph) processVertex(queue chan *Vertex, wg *sync.WaitGroup) {
    defer wg.Done()

    for current := range queue {
        fmt.Printf("頂点 %d (距離: %d) を探索\n", current.id, current.distance)

        // 隣接頂点を探索
        for _, neighborID := range g.adjList[current.id] {
            for _, v := range g.vertices {
                if v.id == neighborID {
                    g.mu.Lock()
                    if !v.visited {
                        v.visited = true
                        v.distance = current.distance + 1
                        queue <- v
                        wg.Add(1)
                    }
                    g.mu.Unlock()
                }
            }
        }
    }
}

func main() {
    // グラフの作成
    g := Graph{
        vertices: []*Vertex{},
        adjList:  make(map[int][]int),
    }

    // 頂点の追加
    for i := 1; i <= 6; i++ {
        g.AddVertex(i)
    }

    // 辺の追加
    g.AddEdge(1, 2)
    g.AddEdge(1, 3)
    g.AddEdge(2, 4)
    g.AddEdge(2, 5)
    g.AddEdge(3, 6)

    // 幅優先探索の実行
    fmt.Println("並行処理による幅優先探索の開始:")
    g.ConcurrentBFS(1)
}

まとめ

本記事では、Go言語で幅優先探索を実装する際に遭遇した奇妙な挙動とその原因、解決策について解説しました。

  • 要点1: Go言語のチャネルとゴルーチンを活用した並行処理の実装方法
  • 要点2: チャネルのバッファサイズ不足が原因で発生する問題とその解決策
  • 要点3: ミューテックスを使用した競合状態の防止方法

この記事を通して、Go言語での並行処理の実装における重要なポイントを理解できたと思います。特に、チャネルのバッファサイズの適切な設定と、ミューテックスを使用した安全なデータ共有の方法は、Go言語での並行処理の実装において非常に重要です。

今後は、この知識を基に、より複雑なグラフアルゴリズムの並列化や、他の並行処理パターンの実装についても記事にする予定です。

参考資料