いろんなアルゴリズム"00.00.00.0e"

立ち位置・仕様

• いろんなアルゴリズムをコピペできるように記録するのみ
• 最適化が目的でない
• たまにメモとして解説を残す
• 最低限でまとめる
• データを抽出しやすいように個別のIDを付与
• あるアルゴリズムにおいて、他のアルゴリズムが登場する際にはそのIDを付与
• IDは16進数表記
• なるべく最低限なパッケージで実装
• なるべく特殊なオブジェクト型は使用しない

TargetID

00.00.00.0e

ReferenceID

幅優先探索（breadth first search）

def breadthFirstSearch(graph_dict, start, goal):
	# graph_dictは有向グラフ
	# keyがparent、valueがchildren
	# 親ノードが一つのみの場合

	queue_list = [(start, [start])]
	visitedNode_list = []

	flag = False
	path = None

	while True:
		if not queue_list:
			flag = False
			break
		node,path = queue_list[0]
		queue_list = queue_list[1:]
		
		if node == goal:
			flag = True
			break
		if node not in visitedNode_list:
			visitedNode_list.append(node)
			for child in graph_dict[node]:
				if child not in visitedNode_list:
					queue_list.append((child, path + [child]))

	if flag:
		return path
	else:
		return None

使用方法

graph_dict = {
    1:[2,3],
    2:[4],
    3:[5,6,7],
    4:[8],
    5:[],
    6:[9],
    7:[],
    8:[],
    9:[]}
print(breadthFirstSearch(graph_dict,1,9)) # [1, 3, 6, 9]
# visitedNode_list = [1, 2, 3, 4, 5, 6, 7, 8]