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

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