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

我有一个网络（无向图），其由下面的稀疏矩阵来表示：MATLAB：在无向图中找到强连通分量

% 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条目，因此简单的搜索算法可能太慢。非常感谢！

来源

2015-12-28 NicoDean

我不认为MATLAB有内置的东西来做这样的事情，但基本上你在找什么是Kosaraju Sharir算法，它是最强大的连接组件的发现算法。它很小且相当容易实施。看看这里： https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm –

谢谢。不幸的是，Kosaraju算法仅适用于有向图。但是，我的图形是无向的。我没有发现任何适应无向情况。你是否也有无向图的解决方案？谢谢！ – NicoDean

我不明白为什么这个问题“搁置”。这是一个非常有效的请求，可以帮助您找到一种使用matlab解决特定问题的良好方法（详细描述，即使使用图像）。有人（@adriaan Dan-Cornilescu aschipfl Himanshu bigOTHER）请向我解释这一点。 – NicoDean

首先，由于这是一个无向图，没有强连接的概念。我错看了这个重要的细节。现在，两个红色圆圈之间用一条边相连，如果我们要从图中去除边缘，的连接组件增加1（至2）。所以给定一个无向图，真正的问题是“是否存在一个边（或多个边），删除哪个会增加连接组件的数量？”。我可以想到在线上的蛮力算法：

删除n1和n2之间的边e。
n1和n2之间还有路径吗？
是：这不是一个候选边缘，去1
编号：好，删除该边缘将打破图形，捞出去1

最终连接组件的数量将已经增加了删除边缘的数量。复杂度为O（N * E）（O（N），用于在去除每条边后找到n1和n2之间的路径）。您可能需要更改图表表示以有效地执行此操作。

来源

2015-12-28 22:50:06

谢谢你，这是非常聪明的（通过消除边缘来查看图的突破），对此没有任何关注。我相信也可以推广到n去除的边缘。谢谢！ – NicoDean

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

回答

相关问题