为 SCC 实现 Kosaraju 算法

Question

我正在尝试实现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)

但是对于更大的图需要很长的时间。如何对此进行优化？

Answer 1

好问题。您的实现似乎在速度方面进行了相应的优化。在改进Kosaraju算法的实现方面，您没有什么可做的。然而，还有其他算法可以在更快的时间内找到SCC。特别是，您应该查看：

• Tarjan的强连通分量算法
• 基于路径的强分量算法

这些算法，就像Kosaraju的算法一样，在O(V+E(中运行。然而，这些其他算法的常数比Kosaraju的算法小。