友達のつながりをGraphとBFSで表現する

やりたいこと

SNSで、よく見る「友達かも」という表示。
友達の友達（2次の繋がり）が、フォローする対象として表示される。
友達の繋がりを一覧で表示する。

前提知識

Graph構造

Graph構造は、nodeとedge（辺）から成る。
nodeは、複数のnodeと繋がることができる。
nodeとnodeの繋がりをedgeと呼ぶ。

BFS (Breadth-First Search)

幅探索とも呼ばれる。
下のようにGraph構造を階層と見立てて、1層ずつ全て巡って、順に深く（開始nodeから遠く）探索していく。

https://inginious.org/course/competitive-programming/graphs-bfs

Queue

FIFO (First-In, First-Out)で、ロケット鉛筆方式のデータ構造。
訪問したnodeをqueueにpushして、次の階層の探索が始まると、1つずつpopしていく。

課題と実装

課題

友達関係が次のようになっている時、あるnodeから見たときの友好関係の次数を一覧化する。

        A
       / \
      B   C
     / \   \
    D   E   F
         \ /
          F

実装

package main

import "fmt"

func main() {
	graph := map[string][]string{
		"A": {"B", "C"},
		"B": {"A", "D", "E"},
		"C": {"A", "F"},
		"D": {"B"},
		"E": {"B", "F"},
		"F": {"C", "E"},
	}

	distanceMap := FindConnections(graph, "A")

	for node, distance := range distanceMap {
		fmt.Printf("- %sは%d次のつながり\n", node, distance)
	}
}

func FindConnections(graph map[string][]string, start string) map[string]int {
	// 一度訪れたnodeは、visitedにmapで保管し、訪問されたらvalueをtrueにする
	// makeした時点で、vlaueには全て初期値のfalseが自動的に入っている
	visited := make(map[string]bool, len(graph))

	// 各nodeの、開始nodeからの距離を記録する
	// これもまた、makeした時点でvalueに0が入る
	distance := make(map[string]int, len(graph))

	// 開始時点で、すでに開始nodeは訪問していると考えることができる
	visited[start] = true

	// 開始nodeからそれ自身の距離は0と表現できる
	distance[start] = 0

	// まず開始nodeを詰めておいて、ループが始まったらすぐpopする
	queue := []string{start}

	// while文で、queueが空になるまで繰り返す
	// iterationをする中で、queueからnodeがpopやpushされる
	for len(queue) > 0 {
		current := queue[0]

		// pop
		queue = queue[1:]

		for _, neighbor := range graph[current] {
			if !visited[neighbor] {

				// 訪問したのでtrue
				visited[neighbor] = true

				// distanceは、current + 1なのがポイント
				// A - B - Dと繋がっていて、DからAの距離を知りたい時、AからBの距離に、1を足したものがそれになる
				distance[neighbor] = distance[current] + 1

				// push
				queue = append(queue, neighbor)
			}
		}
	}

	return distance
}

output

% go run main.go
- Aは0次のつながり
- Bは1次のつながり
- Cは1次のつながり
- Dは2次のつながり
- Eは2次のつながり