Goでのアルゴリズムクイックリファレンス第2版(幅優先探索)

Goに慣れるためとアルゴリズムの復習の為に週1ぐらいで更新していきます。アルゴリズムクイックリファレンス 第2版を読んで各種アルゴリズムをGoで実装して行きます。

前回: Goでのアルゴリズムクイックリファレンス第2版(深さ優先探索)

今回は幅優先探索

幅優先探索（はばゆうせんたんさく、英: breadth first search）はグラフ理論(Graph theory)において木構造(tree structure)やグラフ(graph)の探索に用いられるアルゴリズム。アルゴリズムは根ノードで始まり隣接した全てのノードを探索する。それからこれらの最も近いノードのそれぞれに対して同様のことを繰り返して探索対象ノードをみつける。「横型探索」とも言われる。

package main

import (
    "container/list"
    "fmt"
)

type Graph struct {
    List []int
}

func BreadthFirstSearch(g *[]*Graph, n int, visited *[]int) {
    (*visited)[n] = 1

    q := list.New()
    q.PushBack(n)

    for {
        if q.Len() == 0 {
            break
        }
        n := q.Remove(q.Front())
        fmt.Printf("n:%d\n", n)
        fmt.Println(*visited)
        for _, v := range (*g)[n.(int)].List {
            if (*visited)[v] == 0 {
                (*visited)[v] = 1
                fmt.Printf("\tn:%d->%d\n", n, v)
                q.PushBack(v)
            }
        }
    }
}

func main() {
    g := make([]*Graph, 0)
    g = append(g, &Graph{[]int{5, 6}}) // 0
    g = append(g, &Graph{[]int{3, 4}}) // 1
    g = append(g, &Graph{[]int{1}})    // 2
    g = append(g, &Graph{[]int{4}})    // 3
    g = append(g, &Graph{[]int{3}})    // 4
    g = append(g, &Graph{[]int{0}})    // 5
    g = append(g, &Graph{[]int{7}})    // 6
    g = append(g, &Graph{[]int{2}})    // 7

    visited := make([]int, len(g))
    BreadthFirstSearch(&g, 0, &visited)
}

次回はダイクストラ法です。