MATLAB：在无向图中寻找强连通分量

Question

我有一个网络（无向图），由以下稀疏矩阵表示：

 %  A B C D E F G H I J K L M
mm=[0 0 1 1 0 0 1 0 0 0 0 0 0; % A
    0 0 0 0 1 0 0 0 0 0 1 0 0; % B
    1 0 0 1 0 1 0 0 0 0 0 1 0; % C
    1 0 1 0 0 0 0 0 0 0 0 0 0; % D
    0 1 0 0 0 0 0 0 0 0 0 0 1; % E
    0 0 1 0 0 0 1 0 0 0 0 0 1; % F
    1 0 0 0 0 1 0 0 0 0 0 1 0; % G
    0 0 0 0 0 0 0 0 1 1 0 0 1; % H
    0 0 0 0 0 0 0 1 0 1 0 0 0; % I
    0 0 0 0 0 0 0 1 1 0 1 0 1; % J
    0 1 0 0 0 0 0 0 0 1 0 0 0; % K
    0 0 1 0 0 0 1 0 0 0 0 0 0; % L
    0 0 0 0 1 1 0 1 0 1 0 0 0; % M
   ]; 
xx=tril(mm + mm');
view(biograph(sparse(xx),[],'ShowArrows','off','ShowWeights','off'))

在这个网络中，有两个强互连的子网：

是否有一些聪明的算法来识别这种强连接的子网络？

请注意，我的矩阵相当大，约 10.000x10.000 个条目，因此简单的搜索算法可能太慢。非常感谢！

Answer 1

首先，由于这是一个无向图，所以没有强联系的概念。我看错了这个重要的细节。现在，两个红色圆圈由一条边连接，如果我们要从图中删除这条边，则没有。连接组件的数量增加 1（到 2）。所以给定一个无向图，真正的问题是"Does there exist an edge(or edges), removing which would increase the number of connected components ?"。我可以想到在线上的蛮力算法：

去掉n1和n2之间的一条边e。
n1和n2之间还有路径吗？
是：这不是候选边，转到1
否：很好，删除这条边会破坏图形，删除并转到 1

最后，连接组件的数量会随着删除边的数量而增加。复杂度为 O(N*E)（O(N) 用于在移除每条边后找到 n1 和 n2 之间的路径）。您可能需要更改图形表示才能有效地执行此操作。

MATLAB：在无向图中寻找强连通分量

MATLAB: Finding strongly connected components in undirected graph

algorithm

networking

matlab

graph

graph-algorithm