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

立ち位置・仕様

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

TargetID

00.00.00.0d

ReferenceID

深さ優先探索（depth first search）

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

	flag = False

	while True:
		if not stack_list:
			flag = False
			break
		node = stack_list[-1]
		if node == goal:
			flag = True
			break
		children_list = graph_dict[node]
		child = None
		for c in children_list: 
			if c not in visitedNode_list:
				child = c
				break
		if child == None:
			stack_list = stack_list[:-1]
		else:
			visitedNode_list.append(child)
			stack_list.append(child)
	if flag:
		return stack_list
	else:
		return None

使用方法

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