1

Tarjan の強連結グラフ アルゴリズム ( https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm ) を実装しようとしています。ここに私のコードがあり、なぜ頂点4と頂点5も強連結成分として出力されるのか混乱していますか?

テストするノードが 5 つしかない非常に単純なダイアグラムを使用しています。私のコードは Python 2.7 で書かれています。

from collections import defaultdict
class SccGraph:
    def __init__(self, vertex_size):
        self.out_neighbour = defaultdict(list)
        self.vertex = set()
        self.visited = set()
        self.index = defaultdict(int)
        self.low_index = defaultdict(int)
        self.global_index = 0
        self.visit_stack = []
        self.scc = []
    def add_edge(self, from_node, to_node):
        self.vertex.add(from_node)
        self.vertex.add(to_node)
        self.out_neighbour[from_node].append(to_node)
    def dfs_graph(self):
        for v in self.vertex:
            if v not in self.visited:
                self.dfs_node(v)
    def dfs_node(self, v):
        # for safe protection
        if v in self.visited:
            return
        self.index[v] = self.global_index
        self.low_index[v] = self.global_index
        self.global_index += 1
        self.visit_stack.append(v)
        self.visited.add(v)
        for n in self.out_neighbour[v]:
            if n not in self.visited:
                self.dfs_node(n)
                self.low_index[v] = min(self.low_index[v], self.low_index[n])
            elif n in self.visit_stack:
                self.low_index[v] = min(self.low_index[v], self.index[n])
        result = []
        if self.low_index[v] == self.index[v]:
            w = self.visit_stack.pop(-1)
            while w != v:
                result.append(w)
                w = self.visit_stack.pop(-1)
            result.append(v)
            self.scc.append(result)

if __name__ == "__main__":
    g = SccGraph(5)
    # setup a graph 1->2->3 and 3 -> 1 which forms a scc
    # setup another two edges 3->4 and 4->5
    g.add_edge(1,2)
    g.add_edge(2,3)
    g.add_edge(3,1)
    g.add_edge(3,4)
    g.add_edge(4,5)
    g.dfs_graph()
    print g.scc
4

1 に答える 1

1

すべての頂点が強くつながっています。それがより大きな強く接続されたサブグラフに属していない場合、それはすでに強いコンポーネントです。したがって、実装と Tarjan のアルゴリズムの両方に問題はありません。（他に間違いがあるかどうかは確認していません）。

于 2017-01-07T23:27:06.197 に答える