{"content":"

强连通分量

我们认为有向图中的两个节点U和V属于同一强连通分量[SCC]，如果存在从U到V的路径和从V到U的路径。

找到所有SCC的算法是惊人的简单和相当聪明。

（1）在图G上运行深度优先搜索[dfs]并记住DFS从节点完成搜索的时间

（2）通过倒转G中的边方向创建图G‘

（3）按降时给出的顺序在图G‘上运行DFS

（4）步骤3中可从节点U到达的所有节点形成单个SCC

看照片。图G包含编号为1，2，3的SCC。当我们将G中的每个分量收缩成一个节点时，我们得到一个新的图T，它是有向的，无圈的。当DFS从节点U中搜索G时，当U的组件中的所有节点都耗尽时(如果可能从U中到达另一个SCC)，则停止。如果你看图T，组件的完成时间是：时间(1)=3，时间(2)=2，时间(3)=1。然后，第二个DFS被迫以1，2，3的顺序运行在一个反图G‘/T’上。这一次，DFS正是在当前强连接组件中的所有节点耗尽时停止的。

实现代码

图一

测试一

图二

测试二

图三

测试三

","codes":[null,{"_id":"cvfjf","code":"import networkx as nx\r\nimport matplotlib.pyplot as plt\r\n\r\n%matplotlib inline\r\ndef strongly_connected_components(graph):\r\n times, _ = depth_first_search(graph.nodes(), graph)\r\n _, components = depth_first_search(reversed(times), graph.reverse())\r\n\r\n return components\r\ndef depth_first_search(nodes, graph):\r\n times, components, explored = [], [], set()\r\n\r\n for node in nodes:\r\n component = []\r\n stack = [(False, node)]\r\n\r\n while stack:\r\n complete, i = stack.pop()\r\n\r\n # check if already processed\r\n if complete:\r\n times.append(i)\r\n continue\r\n elif i in explored:\r\n continue\r\n\r\n # mark the node\r\n component.append(i)\r\n explored.add(i)\r\n\r\n # search in depth\r\n stack.append((True, i))\r\n stack.extend((False, i) for i in graph[i])\r\n\r\n if component:\r\n components.append(component)\r\n\r\n return times, components","options":{}},{"_id":"akpem","code":"graph = nx.DiGraph()\r\ngraph.add_nodes_from(range(6))\r\ngraph.add_edges_from([\r\n (0, 1), (1, 2), (2, 0), \r\n (3, 4), (4, 5), (5, 3),\r\n (0, 5), (2, 3),\r\n])\r\nplt.figure(figsize=(8, 8))\r\nplt.axis('off')\r\nnx.draw_networkx(graph, pos=nx.circular_layout(graph), node_size=400, node_color='steelblue', font_color='white')","options":{}},null,{"_id":"qoveo","code":"strongly_connected_components(graph)","options":{}},{"_id":"dyqup","code":"graph = nx.DiGraph()\r\ngraph.add_nodes_from(range(7))\r\ngraph.add_edges_from([\r\n (0, 1), (1, 2), (2, 0), \r\n (0, 3), (3, 4), (4, 0),\r\n (0, 5), (5, 6), (6, 0),\r\n])\r\nplt.figure(figsize=(8, 8))\r\nplt.axis('off')\r\nnx.draw_networkx(graph, node_size=400, node_color='steelblue', font_color='white')","options":{}},null,{"_id":"egwaz","code":"strongly_connected_components(graph)","options":{}},{"_id":"oqbrq","code":"graph = nx.DiGraph()\r\ngraph.add_nodes_from(range(7))\r\ngraph.add_edges_from([\r\n (0, 2), (2, 4), (4, 6), (6, 0),\r\n (0, 1), (2, 3), (4, 5), (6, 7),\r\n])\r\nplt.figure(figsize=(8, 8))\r\nplt.axis('off')\r\nnx.draw_networkx(graph, pos=nx.circular_layout(graph), node_size=400, node_color='steelblue', font_color='white')","options":{}},null,{"_id":"skjym","code":"strongly_connected_components(graph)","options":{}},null]}

Day 95：强连通分量

强连通分量

实现代码

图一

测试一

图二

测试二

图三

测试三