Note: This page has been translated by MathWorks. Please click here

To view all translated materals including this page, select Japan from the country navigator on the bottom of this page.

To view all translated materals including this page, select Japan from the country navigator on the bottom of this page.

Find strongly or weakly connected components in graph

`[`

* S*,

`C`

`G`

[

`S`

`C`

`G`

`DirectedValue`

[

`S`

`C`

`G`

`WeakValue`

`G` | N-by-N sparse matrix that represents a graph. Nonzero entries
in matrix indicate the presence of an
edge.`G` |

`DirectedValue` | Property that indicates whether the graph is directed or undirected.
Enter `false` for an undirected graph. This results
in the upper triangle of the sparse matrix being ignored. Default
is `true` . A DFS-based algorithm computes the
connected components. Time complexity is |

`WeakValue` | Property that indicates whether to find weakly connected components
or strongly connected components. A weakly connected component is
a maximal group of nodes that are mutually reachable by violating
the edge directions. Set to `WeakValue` `true` to
find weakly connected components. Default is `false` ,
which finds strongly connected components. The state of this parameter
has no effect on undirected graphs because weakly and strongly connected
components are the same in undirected graphs. Time complexity is `O(N+E)` ,
where `N` and `E` are number of
nodes and edges respectively. |

For introductory information on graph theory functions, see Graph Theory Functions.

`[`

finds the
strongly connected components of the graph represented by matrix * S*,

`C`

`G`

`G`

`G`

`G`

The number of components found is returned in * S*,
and

`C`

Tarjan's algorithm has a time complexity of `O(N+E)`

,
where `N`

and `E`

are the number
of nodes and edges respectively.

`[`

calls * S*,

`C`

`G`

`PropertyName`

`PropertyValue`

`graphconncomp`

with
optional properties that use property name/property value pairs. You
can specify one or more properties in any order. Each `PropertyName`

```
[
```

indicates whether the graph
is directed or undirected. Set * S*,

`C`

`G`

`DirectedValue`

`directedValue`

`false`

for
an undirected graph. This results in the upper triangle of the sparse
matrix being ignored. Default is `true`

. A DFS-based
algorithm computes the connected components. Time complexity is `O(N+E)`

,
where `N`

and `E`

are number of
nodes and edges respectively.`[`

indicates whether to find weakly
connected components or strongly connected components. A weakly connected
component is a maximal group of nodes that are mutually reachable
by violating the edge directions. Set * S*,

`C`

`G`

`WeakValue`

`WeakValue`

`true`

to
find weakly connected components. Default is `false`

,
which finds strongly connected components. The state of this parameter
has no effect on undirected graphs because weakly and strongly connected
components are the same in undirected graphs. Time complexity is `O(N+E)`

,
where `N`

and `E`

are number of
nodes and edges respectively.By definition, a single node can be a strongly connected component.

A directed acyclic graph (DAG) cannot have any strongly connected components larger than one.

Create and view a directed graph with 10 nodes and 17 edges.

`DG = sparse([1 1 1 2 2 3 3 4 5 6 7 7 8 9 9 9 9], ... [2 6 8 3 1 4 2 5 4 7 6 4 9 8 10 5 3],true,10,10) DG = (2,1) 1 (1,2) 1 (3,2) 1 (2,3) 1 (9,3) 1 (3,4) 1 (5,4) 1 (7,4) 1 (4,5) 1 (9,5) 1 (1,6) 1 (7,6) 1 (6,7) 1 (1,8) 1 (9,8) 1 (8,9) 1 (9,10) 1 h = view(biograph(DG));`

Find the number of strongly connected components in the directed graph and determine to which component each of the 10 nodes belongs.

[S,C] = graphconncomp(DG) S = 4 C = 4 4 4 1 1 2 2 4 4 3

Color the nodes for each component with a different color.

colors = jet(S); for i = 1:numel(h.nodes) h.Nodes(i).Color = colors(C(i),:); end

[1] Tarjan, R.E., (1972). Depth first search
and linear graph algorithms. SIAM Journal on Computing *1(2)*,
146–160.

[2] Sedgewick, R., (2002). Algorithms in C++, Part 5 Graph Algorithms (Addison-Wesley).

[3] Siek, J.G., Lee, L-Q, and Lumsdaine, A. (2002). The Boost Graph Library User Guide and Reference Manual, (Upper Saddle River, NJ:Pearson Education).

Was this topic helpful?