Main Content

conncomp

图的连通分量

全页折叠

语法

bins = conncomp(G)
bins = conncomp(G,Name,Value)
[bins,binsizes] = conncomp(___)

说明

bins = conncomp(G) 以 bin 形式返回图 G 的连通分量。bin 编号指示图中的每个节点所属的分量。

  • 如果 G 是无向图，则有路径相连的两个节点属于同一分量。

  • 如果 G 是有向图，则仅当两个节点之间存在一条双向连接路径时，这两个节点才属于同一强分量。

示例

bins = conncomp(G,Name,Value) 使用一个或多个名称-值对组参量指定的其他选项。例如，conncomp(G,'OutputForm','cell') 返回一个元胞数组来描述连通分量。

示例

[bins,binsizes] = conncomp(___) 还返回连通分量的大小。binsizes(i) 会给出分量 i 中的节点数量。

示例

全部折叠

打开实时脚本

创建并绘制一个具有三个连通分量的无向图。使用 conncomp 确定每个节点所属的分量。

G = graph([1 1 4],[2 3 5],[1 1 1],6);
plot(G)

Figure contains an axes object. The axes object contains an object of type graphplot.

bins = conncomp(G)
bins = 1×6

     1     1     1     2     2     3
打开实时脚本

创建和绘制一个有向图，然后计算强连通分量和弱连通分量。弱连通分量会忽略连接边的方向。

s = [1 2 2 3 3 3 4 5 5 5 8 8];
t = [2 3 4 1 4 5 5 3 6 7 9 10];
G = digraph(s,t);
plot(G,'Layout','layered')

Figure contains an axes object. The axes object contains an object of type graphplot.

str_bins = conncomp(G)
str_bins = 1×10

     4     4     4     4     4     6     5     1     3     2


weak_bins = conncomp(G,'Type','weak')
weak_bins = 1×10

     1     1     1     1     1     1     1     2     2     2
打开实时脚本

使用 conncomp 的第二个输出提取图的最大分量或删除低于某个大小的分量。

创建并绘制一个有向图。该图有一个大分量、一个小分量和几个只包含一个节点的分量。

s = [1 2 2 3 3 3 4 5 5 5 8 8 9];
t = [2 3 4 1 4 5 5 3 6 7 9 10 10];
G = digraph(s,t,[],20);
plot(G,'Layout','layered')

Figure contains an axes object. The axes object contains an object of type graphplot.

计算弱连通分量并指定 conncomp 的两个输出，以获取每个分量的大小。

[bin,binsize] = conncomp(G,'Type','weak')
bin = 1×20

     1     1     1     1     1     1     1     2     2     2     3     4     5     6     7     8     9    10    11    12


binsize = 1×12

     7     3     1     1     1     1     1     1     1     1     1     1

使用 binsize 提取图的最大分量。idx 是一个逻辑索引，指示每个节点是否属于最大分量。subgraph 函数从 G 中提取由 idx 选择的节点。

idx = binsize(bin) == max(binsize);
SG = subgraph(G, idx);
plot(SG)

Figure contains an axes object. The axes object contains an object of type graphplot.

binsizes 的一个类似用途是根据大小滤出分量。此过程与提取最大分量类似，不过在这一示例中，每个节点可以属于满足大小要求的任何分量。

滤出 G 中少于 3 个节点的任何分量。idx 是逻辑索引，指示每个节点是否属于具有 3 个或更多节点的分量。

idx = binsize(bin) >= 3;
SG = subgraph(G, idx);
plot(SG)

Figure contains an axes object. The axes object contains an object of type graphplot.

输入参数

全部折叠

输入图，指定为 graph 或 digraph 对象。可使用 graph 创建一个无向图，或使用 digraph 创建一个有向图。

示例: G = graph(1,2)

示例: G = digraph([1 2],[2 3])

名称-值参数

将可选的参量对组指定为 Name1=Value1,...,NameN=ValueN，其中 Name 是参量名称，Value 是对应的值。名称-值参量必须出现在其他参量之后，但参量对组的顺序无关紧要。

在 R2021a 之前，使用逗号分隔每个名称和值，并用引号将 Name 引起来。

示例: bins = conncomp(G,'OutputForm','cell')

输出的类型，指定为逗号分隔的对组，其中包含 'OutputForm' 和 'vector' 或 'cell' 中的任一项。

选项输出
'vector'（默认值）bins 是数值向量，指示每个节点所属的连通分量。
'cell'bins 是元胞数组，bins{j} 包含属于分量 j 的所有节点的节点 ID。

注意

'Type' 选项仅适用于使用 digraph 创建的有向图。

连通分量的类型，指定为逗号分隔的对组，其中包含 'Type' 和 'strong'（默认值）或 'weak' 中的任一项。

选项结果
'strong'（默认值）仅当两个节点之间存在一条双向连接路径时，这两个节点才属于同一连通分量。
'weak'只要两个节点之间存在一条连接路径（无论边的方向如何），这两个节点即属于同一连通分量。

示例: bins = conncomp(G,'Type','weak') 计算有向图 G 的弱连通分量。

输出参量

全部折叠

连通分量，以向量或元胞数组形式返回。bin 编号将图中的每个节点分配给一个连通分量：

  • 如果 OutputForm 是 'vector'（默认值），则 bins 是数值向量，指示每个节点所属的连通分量 (bin)。

  • 如果 OutputForm 是 'cell'，则 bins 是元胞数组，bins{j} 包含属于分量 j 的所有节点的节点 ID。

每个连通分量的大小，以向量形式返回。binsizes(i) 给出分量 i 中的元素数量。binsizes 的长度等于连通分量的数目 max(bins)。

详细信息

全部折叠

弱连通分量

只要两个节点之间存在一条连接路径（无论边的方向如何），这两个节点即属于同一弱连通分量。两个弱连通分量之间不存在任何边。

强和弱分量的概念仅适用于有向图，因为它们对于无向图来说是等价的。

强连通分量

当两个节点之间存在双向连接路径时，这两个节点属于同一强连通分量。两个强连通分量之间可以有边，但这些连接边永远不能构成循环。

强连通分量的 bin 编号方式是：连接两个分量的任何边都是从 bin 编号较小的分量指向 bin 编号较大的分量。

强和弱分量的概念仅适用于有向图，因为它们对于无向图来说是等价的。

扩展功能

基于线程的环境
使用 MATLAB® backgroundPool 在后台运行代码或使用 Parallel Computing Toolbox™ ThreadPool 加快代码运行速度。

版本历史记录

在 R2015b 中推出

另请参阅

| |