概要

最近、アルゴリズムの基礎を学ぼうと思ってなっとく!アルゴリズムって書籍を読んでます。この中にあるサンプルコードはPythonで書かれてるんですが、Goを触ることが多いので自分でGolangに書き直して勉強しようと、そのアウトプットです。

幅優先探索はキューを使って、まず隣接ノードを探索しそのノードに対象がなければ、そのノードの隣接ノードをキューに追加していくというアルゴリズムのため、下記2点を確認することができます。

検索対象が存在するか
存在する場合は、その存在までの最短経路

やってみた

問題は「自分の友達に名前の末尾がyの人がいるか、いなければ友達の友達にいるか、いなければ友達の友達の友達に…」ってな感じです。

グラフを作る

まずはグラフになる友達のリストを作ります。

var graph map[string][]string

func init() {
	graph = make(map[string][]string)
	graph["you"] = []string{"alice", "bob", "claire"}
	graph["bob"] = []string{"tom", "peggy"}
	graph["alice"] = []string{"peggy"}
	graph["claire"] = []string{"olivia", "jonny"}
	graph["tom"] = []string{}
	graph["peggy"] = []string{}
	graph["olivia"] = []string{}
	graph["jonny"] = []string{}
}

あなた(you)には alice, bob, claire の3人の友達がいて、さらに
bob には tom, peggy って友達がいて、さらに…
という関係ですね。

あなたは3人のことを友達と思っていますが、彼らの友達リストにあなたが入っていないという点はツッコミなしで。そういう殺伐とした世界観ということで。

キューを作る

次にキューの構造体と機能を作ります。

type Queue struct {
	items []string
}

func NewQueue() *Queue {
	return &Queue{
		items: []string{},
	}
}

// キューに追加する
func (q *Queue) Enqueue(items []string) {
	q.items = append(q.items, items...)
}

// キューから取り出してその値を返す
func (q *Queue) Dequeue() string {
	person := q.items[0]
	q.items = q.items[1:]

	return person
}

Pythonの場合は deque() で簡単にキューを作ることができるそうですが、Goにはないので簡単な形で自作します。

処理を作る

続いてこのグラフに対する幅優先探索の処理です。

func breadthFirstSearch(name string) (bool, string) {
	q := NewQueue()
	q.Enqueue(graph[name])
	searched := []string{}

	for len(q.items) != 0 {
		person := q.Dequeue()
  		// 探索済みの人だった場合はスキップ
		if slices.Contains(searched, person) {
			continue
		}
  
		if person[len(person)-1:] == "y" {
			return true, person
		} else {
			q.Enqueue(graph[person])
			searched = append(searched, person)
		}
	}

	return false, "none"
}

探索済みの人はスキップしないと無限ループに陥る可能性があります。
例えば bob のリストに tom がいて、tom のリストに alice がいて、 alice のリストに bob がいる時、末尾にyがつかないので、この3人でキューをぐるぐる回ることになります。

最終的なコード

こんな感じになりました。

package main

import (
	"fmt"
	"slices"
)

var graph map[string][]string

func init() {
	graph = make(map[string][]string)
	graph["you"] = []string{"alice", "bob", "claire"}
	graph["bob"] = []string{"tom", "peggy"}
	graph["alice"] = []string{"peggy"}
	graph["claire"] = []string{"olivia", "jonny"}
	graph["tom"] = []string{}
	graph["peggy"] = []string{}
	graph["olivia"] = []string{}
	graph["jonny"] = []string{}
}

func main() {
	result, person := breadthFirstSearch("you")
	fmt.Println(result, person)
}

func breadthFirstSearch(name string) (bool, string) {
	q := NewQueue()
	q.Enqueue(graph[name])
	searched := []string{}

	for len(q.items) != 0 {
		person := q.Dequeue()
		if slices.Contains(searched, person) {
			continue
		}
		if person[len(person)-1:] == "y" {
			return true, person
		} else {
			q.Enqueue(graph[person])
			searched = append(searched, person)
		}
	}

	return false, "none"
}

type Queue struct {
	items []string
}

func NewQueue() *Queue {
	return &Queue{
		items: []string{},
	}
}

func (q *Queue) Enqueue(items []string) {
	q.items = append(q.items, items...)
}

func (q *Queue) Dequeue() string {
	person := q.items[0]
	q.items = q.items[1:]

	return person
}

これを実行すると true peggy が出力されます。
友達リストのpeggyを、末尾がyでない形にすれば true jonny が出力されます。
末尾がyの人がいなければ false none が出力されます

あとがき

このケースのグラフは配列形式でしたが、二分木の問題なんかでも使われている印象です。

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

このアルゴリズムを実際に使うか使わないかではなく、こういった学習を通して柔軟な発想や複雑な仕様を理解できるようになりたいですね😌