Main Content

本页的翻译已过时。点击此处可查看最新英文版本。

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. The axes 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. The axes 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. The axes 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. The axes 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. The axes contains an object of type graphplot.

输入参数

全部折叠

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

示例: G = graph(1,2)

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

名称-值对组参数

指定可选的、以逗号分隔的 Name,Value 对组参数。Name 为参数名称,Value 为对应的值。Name 必须放在引号中。您可采用任意顺序指定多个名称-值对组参数,如 Name1,Value1,...,NameN,ValueN 所示。

示例: 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 编号较大的分量。

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

另请参阅

| |

在 R2015b 中推出