[Python] DFSによるグラフの探索

無向グラフをDFSで探索するアルゴリズムを Python で記述します。

グラフは隣接リストを用いて表現します。

深さ優先探索

深さ優先探索（ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう）は、木やグラフを探索するためのアルゴリズムである。

出典: フリー百科事典『ウィキペディア（Wikipedia）』

Wikipedia には、スタックを用いる疑似コードと再帰を用いる疑似コードが載っています。

ここでは、再帰を用いて実装します。

以下のようなグラフの探索を行います。

以前の隣接リストのコードに以下を追記しています。

• 6行目でVertex クラスに visited という訪問済みかどうかのフラグを設定
• 24行目に visited を設定する関数
• 33行目でGraph クラスに __iter__ を設定してループを回しやすく修正
• 70行目、77行目に DFS の関数

class Vertex(object):
    def __init__(self, id):
        self.id = id
        self.adjacent = {}
        # DFS
        self.visited = False

    def add_neighbor(self, neighbor, weight=0):
        self.adjacent[neighbor] = weight
    
    def get_neighbors(self):
        return self.adjacent

    def get_connections(self):
        return self.adjacent.keys()  

    def get_vertex_id(self):
        return self.id

    def get_weight(self, neighbor):
        return self.adjacent[neighbor]

    # DFS
    def set_visited(self):
        self.visited = True


class Graph(object):
    def __init__(self):
        self.vertex_dict = {}
        self.num_vertex = 0
    
    # DFS ループで扱いやすくする。
    def __iter__(self):
        return iter(self.vertex_dict.values())

    def add_vertex(self, id):
        self.num_vertex = self.num_vertex + 1
        new_vertex = Vertex(id)
        self.vertex_dict[id] = new_vertex
        return new_vertex

    def get_vertex(self, id):
        if id in self.vertex_dict:
            return self.vertex_dict[id]
        else:
            return None

    def add_edge(self, frm, to, weight=0):
        if frm not in self.vertex_dict:
            self.add_vertex(frm)
        if to not in self.vertex_dict:
            self.add_vertex(to)
        self.vertex_dict[frm].add_neighbor(self.vertex_dict[to], weight)
        # 有向グラフの場合は別
        self.vertex_dict[to].add_neighbor(self.vertex_dict[frm], weight)

    def get_vertices(self):
        return self.vertex_dict.keys()

    def get_edges(self):
        edges = []
        for v in self.vertex_dict.values():
            for w in v.get_connections():
                vid = v.get_vertex_id()
                wid = w.get_vertex_id()
                edges.append((vid, wid, v.get_weight(w)))
        return edges

def dfs(graph, current_vertex, traversal_verticies):
    current_vertex.set_visited()
    traversal_verticies.append(current_vertex.get_vertex_id())
    for neighbor in current_vertex.get_connections(): 
        if not(neighbor.visited):  
            dfs(graph, neighbor, traversal_verticies) 
 
def dfs_traversal(graph):
    for current_vertex in graph:
        traversal_verticies = []
        if not(current_vertex.visited):  
            dfs(graph, current_vertex, traversal_verticies) 
        if traversal_verticies:
            print(f'start from {current_vertex.get_vertex_id()}:', traversal_verticies)
    

if __name__ == '__main__':

    graph = Graph()
    graph.add_vertex('a')
    graph.add_vertex('b')
    graph.add_vertex('c')
    graph.add_vertex('d')
    graph.add_vertex('e')
    graph.add_vertex('f')
    graph.add_edge('a', 'b', 1)  
    graph.add_edge('a', 'c', 1)
    graph.add_edge('a', 'e', 1)
    graph.add_edge('b', 'd', 1)
    graph.add_edge('b', 'e', 1)
    graph.add_edge('c', 'd', 1)
    graph.add_edge('c', 'e', 1)
    graph.add_edge('d', 'e', 1)
    
    dfs_traversal(graph)
    # start from a: ['a', 'b', 'd', 'c', 'e']
    # start from f: ['f']

想定通りの結果を得ることができました。