Python で深さ優先探索を実装します。
ノードクラス
幅優先探索と同じです。
各ノードは自身の名前、隣接リスト、訪問済みかどうかのフラグを持ちます。
class Node(object):
def __init__(self, name):
self.name = name
self.adjacency_list = []
self.visited = False
深さ優先探索
__init__は、探索したノードを順に保存する探索順リストを持ちます。
また、探索順リストを表示する show_traversed_path と探索順リストと訪問済みフラグをリセットする reset_lst_traversed という関数を持ちます。
class Node(object):
def __init__(self, name):
self.name = name
self.adjacency_list = []
self.visited = False
class DepthFirsrSearch(object):
def __init__(self):
self.lst_traversed = []
def show_traversed_path(self):
names = []
for node in self.lst_traversed:
names.append(node.name)
print(names)
def reset_lst_traversed(self):
for node in self.lst_traversed:
node.visited = False
self.lst_traversed.clear()
再帰
疑似コードそのままです。
function 深さ優先探索(v)
v に訪問済みの印を付ける
v を処理する
for each v に接続している頂点 i do
if i が未訪問 then
深さ優先探索(i)
class Node(object):
def __init__(self, name):
self.name = name
self.adjacency_list = []
self.visited = False
class DepthFirsrSearch(object):
def __init__(self):
self.lst_traversed = []
def show_traversed_path(self):
names = []
for node in self.lst_traversed:
names.append(node.name)
print(names)
def reset_lst_traversed(self):
for node in self.lst_traversed:
node.visited = False
self.lst_traversed.clear()
def search_rec(self, node):
node.visited = True
self.lst_traversed.append(node)
for n in node.adjacency_list:
if not n.visited:
self.search_rec(n)
スタック
こちらも疑似コードそのままですが、 隣接リストをスタックに積む順番により再帰と探索順が異なる結果になるので、 search_stack_2 として再帰と同じ順番で探索する関数も実装します。
function 深さ優先探索(v)
S ← 空のスタック
v を S に積む
while S が空ではない do
v ← S から取り出す
if v が未訪問 then
v に訪問済みの印を付ける
v を処理する
for each v に接続している頂点 i do
if i が未訪問 then
i を S に積む
class Node(object):
def __init__(self, name):
self.name = name
self.adjacency_list = []
self.visited = False
class DepthFirsrSearch(object):
def __init__(self):
self.lst_traversed = []
def show_traversed_path(self):
names = []
for node in self.lst_traversed:
names.append(node.name)
print(names)
def reset_lst_traversed(self):
for node in self.lst_traversed:
node.visited = False
self.lst_traversed.clear()
def search_rec(self, node):
node.visited = True
self.lst_traversed.append(node)
for n in node.adjacency_list:
if not n.visited:
self.search_rec(n)
def search_stack(self, start_node):
stack = []
stack.append(start_node)
while stack:
current_node = stack.pop()
if not current_node.visited:
current_node.visited = True
self.lst_traversed.append(current_node)
for node in current_node.adjacency_list:
if not node.visited:
stack.append(node)
def search_stack_2(self, start_node):
stack = []
stack.append(start_node)
while stack:
current_node = stack.pop()
if not current_node.visited:
current_node.visited = True
self.lst_traversed.append(current_node)
for node in reversed(current_node.adjacency_list):
if not node.visited:
stack.append(node)
テスト
以下のようなグラフをAからスタートし探索します。
class Node(object):
def __init__(self, name):
self.name = name
self.adjacency_list = []
self.visited = False
class DepthFirsrSearch(object):
def __init__(self):
self.lst_traversed = []
def show_traversed_path(self):
names = []
for node in self.lst_traversed:
names.append(node.name)
print(names)
def reset_lst_traversed(self):
for node in self.lst_traversed:
node.visited = False
self.lst_traversed.clear()
def search_rec(self, node):
node.visited = True
self.lst_traversed.append(node)
for n in node.adjacency_list:
if not n.visited:
self.search_rec(n)
def search_stack(self, start_node):
stack = []
stack.append(start_node)
while stack:
current_node = stack.pop()
if not current_node.visited:
current_node.visited = True
self.lst_traversed.append(current_node)
for node in current_node.adjacency_list:
if not node.visited:
stack.append(node)
def search_stack_2(self, start_node):
stack = []
stack.append(start_node)
while stack:
current_node = stack.pop()
if not current_node.visited:
current_node.visited = True
self.lst_traversed.append(current_node)
for node in reversed(current_node.adjacency_list):
if not node.visited:
stack.append(node)
if __name__ == '__main__':
a = Node('A')
b = Node('B')
c = Node('C')
d = Node('D')
e = Node('E')
f = Node('F')
g = Node('G')
a.adjacency_list.extend([b, c, e])
b.adjacency_list.extend([a, d, f])
c.adjacency_list.extend([a, g])
d.adjacency_list.extend([b])
e.adjacency_list.extend([a, f])
f.adjacency_list.extend([b, e])
g.adjacency_list.extend([c])
dfs = DepthFirsrSearch()
dfs.search_rec(a)
# ['A', 'B', 'D', 'F', 'E', 'C', 'G']
dfs.show_traversed_path()
dfs.reset_lst_traversed()
dfs.search_stack(a)
# ['A', 'E', 'F', 'B', 'D', 'C', 'G']
dfs.show_traversed_path()
dfs.reset_lst_traversed()
dfs.search_stack_2(a)
# ['A', 'B', 'D', 'F', 'E', 'C', 'G']
dfs.show_traversed_path()
想定通りの探索順になりました。