conncomp

Componentes conexos de um grafo ou dígrafo.

Categoria: Mathematics > Graph and Network Algorithms

Sintaxe

bins = conncomp(G)

[bins, binsizes] = conncomp(G)

bins = conncomp(G, 'Type', 'strong')

Descrição

Em um grafo não direcionado, um componente é um conjunto maximal de nós que se alcançam mutuamente. Nós isolados formam componentes de tamanho um. Para achar o maior componente, use [~, k] = max(binsizes) e selecione os nós em que bins == k.

Em um dígrafo, a versão fraca só pergunta se o grafo não direcionado subjacente é conexo, enquanto a forte exige caminhos dirigidos nos dois sentidos.

Argumentos de entrada

G

Um graph ou digraph.

'Type'

'weak' (padrão) ignora as direções das arestas; 'strong' exige caminho dirigido nos dois sentidos.

Argumentos de saída

bins

Vetor linha com um rótulo de componente por nó.

binsizes

Número de nós em cada componente, indexado pelo rótulo.

Exemplo

Três pedaços

G = graph([1 2 4 5 7], [2 3 5 6 8]);
[bins, sizes] = conncomp(G)
[sbins, ssizes] = conncomp(digraph([1 2 3 4], [2 3 1 3]), 'Type', 'strong')

bins = 1×8

     1     1     1     2     2     2     3     3
sizes = 1×3

     3     3     2
sbins = 1×4

     2     2     2     1
ssizes = 1×2

     1     3

Veja também

condensation biconncomp bfsearch isdag