[グラフ] 深さ優先探索をPythonで実装

[グラフ] 深さ優先探索

深さ優先探索 深さ優先探索（ふかさゆうせんたんさく、英:depth-first search, DFS、バックトラック法ともいう）は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始ま...

yottagin.com

2020-02-12 10:43

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()

想定通りの探索順になりました。

[グラフ] ダイクストラ法

最短経路問題 グラフ理論における最短経路問題（さいたんけいろもんだい、英:shortest path problem）とは、重み付きグラフの与えられた2つのノード間を結ぶ経路の中で、重みが最小の経路を求める最適化問題である。 出典: フリー百科事典『...

yottagin.com

2020-02-14 12:20