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

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

前回: Goでのアルゴリズムクイックリファレンス第2版(二分探索木)

今回は深さ優先探索

深さ優先探索（ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう）は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り探索を行う。「縦型探索」とも呼ばれる。

package main

import "fmt"

type Graph struct {
    List []int
}

func DepthFirstSearch(g *[]*Graph, n int, visited *[]int) {
    fmt.Printf("n:%d\n", n)
    (*visited)[n] = 1
    fmt.Println(*visited)
    for _, v := range (*g)[n].List {
        if (*visited)[v] == 0 {
            DepthFirstSearch(g, v, visited)
        }
    }
}

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

    visited := make([]int, len(gl))
    DepthFirstSearch(&gl, 0, &visited)
}

どこからも接続されてないところは訪問する必要性が無いはずなのでこれでいいとは思うんだけど。

次回は幅優先探索です。