Um conjunto X de vértices é isolado se for, ao mesmo tempo, uma fonte e um sorvedouro. Há dois casos degenerados que vale a pena destacar: o conjunto de todos os vértices e o conjunto vazio são isolados.
Um componente
(acho que seria melhor dizer
pedaço
)
de um grafo é um conjunto isolado não vazio minimal.
Em outras palavras,
um componente
é um conjunto isolado que não inclui propriamente nenhum
outro conjunto isolado, exceto o vazio.
Esta é uma boa ocasião para discutir, abstratamente,
a diferença entre minimal
e mínimo
.
Digamos que eu tenho uma coleção A
de conjuntos.
Um elemento X de A
é minimal
se não existe um elemento
Y de A
que seja subconjunto próprio de X.
Um elemento X de A
é mínimo
se não existe um elemento
Y de A
tal que ∣Y∣ < ∣X∣.
Como representar os componentes de um grafo? Podemos atribuir um rótulo a cada vértice de tal forma que dois vértices tenham o mesmo rótulo se e só se pertencem ao mesmo componente. O seguinte algoritmo calcula tais rótulos:
para cada vértice v faça rótulo[v] = v
para cada arco (v, w) faça
alpha = rótulo[v]
beta = rótulo[w]
se alpha ≠ beta então
para cada vértice x faça
se rótulo[x] ≡ beta
então rótulo[x] = alpha
Para entender o algoritmo, basta observar que no início de cada iteração, ou seja, a cada passagem pela linha 2, os rótulos identificam corretamente os componentes do grafo (V, A′), onde V é o conjunto de todos os vértices e A′ o conjunto dos arcos já examinados.
No algoritmo acima,
os rótulos são vértices:
para cada vértice v do grafo,
rótulo[v] é o vértice-mestre
do componente que contém v.
Poderíamos igualmente bem ter usado números no papel de rótulos.
O algoritmo poderia ser chamado slow-union-quick-find; ele é exaustivamente discutido na seção 1.2 do livro Algorithms in C de Sedgewick. Na seção 1.3, o livro oferece um alternativa mais rápida (quick-union-slow-find), depois outra ainda mais rápida (weighted version), e finalmente uma excelente (with path compression).
Esse método de identificação de componentes é a base do célebre algoritmo de Kruskal, implementado no módulo MILES_SPAN do SGB. A implementação é ligeiramente diferente das de Sedgewick: ela mantém todos os vértices de um mesmo componente em uma lista circular (veja blocos 16 a 18 do módulo MILES_SPAN e também blocos 3 e 4 do módulo WORD_COMPONENTS).