我正在尝试实现 Kosaraju 的算法，以在线性时间内找到有向图的强连通分量。目标是存储和输出 SCC 大小列表。
class Graph:
def __init__(self, edge_list, num_nodes):
self.graph = edge_list
self.rev_graph = self.reverse_graph()
self.num_nodes = num_nodes
self.traversed_nodes_p1 = []
self.traversed_nodes_p2 = []
self.counter = 0;
self.scc_size_list = []
self.scc_sl()
def reverse_graph(self):
r_graph = [];
for e in self.graph:
tail = e[0];
head = e[1];
r_graph.append([head, tail])
r_graph = sorted(r_graph, key = lambda x: x[0])
return r_graph
def dfs_p1(self, starting_node, g, t_nodes):
if (starting_node not in t_nodes):
t_nodes.insert(0, starting_node)
for i in range (len(g)):
if (g[i][0] == starting_node and g[i][1] not in t_nodes):
self.dfs_p1(g[i][1], g, t_nodes)
def dfs_loop_p1 (self):
for i in range (1, self.num_nodes+1):
self.dfs_p1(i, self.rev_graph, self.traversed_nodes_p1)
def dfs_p2(self, starting_node, g, t_nodes):
if (starting_node not in t_nodes):
self.counter += 1
t_nodes.append(starting_node)
for i in range (len(g)):
if (g[i][0] == starting_node and g[i][1] not in t_nodes):
self.dfs_p2(g[i][1], g, t_nodes)
def dfs_loop_p2 (self):
for i in self.traversed_nodes_p1:
self.counter = 0
self.dfs_p2(i, self.graph, self.traversed_nodes_p2)
if self.counter > 0:
self.scc_size_list.append(self.counter)
def scc_sl (self):
self.dfs_loop_p1()
self.dfs_loop_p2()
self.scc_size_list.sort()
self.scc_size_list.reverse()
此代码为较小的图生成正确的输出（例如 9 个节点，15 条边）
test_edge_list = [[1,2], [1,9], [2,3], [2,8], [3,4], [3,5], [4,5], [6,5], [6,8], [7,6], [7,9], [8,3], [8,7], [9,2], [9,8]]
test = Graph(test_edge_list, 9)
print(test.scc_size_list)
但需要很长时间才能处理更大的图表。我该如何优化呢？