Um grafo não direcionado é conectado se cada par de vértices está conectado por um caminho. Os componentes conectados são as porções conectadas de um grafo. Um grafo não direcionado é conectado se ele tem exatamente um componente conectado.
Os componentes fortemente conexos são os subgrafos maximais fortemente conectados.
Os componentes fortemente conectados de
um grafo direcionado são conjuntos de
vértices sob a relação “são mutuamente
alcançáveis”.
Por exemplo {0, 1, 2, 3}, {4} e {5} são os componentes
fortemente conectados, {4, 5} não o é, pois o
vértice 5 não é alcançável a partir do vértice 4.
O Algoritmo para achar estes componentes é:
- Aplicar a busca em profundidade no grafo G para obter os tempos de término t[u] para cada vértice u.
- Obter o grafo G', que é o grafo transposto, isto é, são os mesmos vértices mas as arestas são invertidas. Assim existe uma arestas (u,v) em G' se existe uma aresta (v,u) em G.
- Aplicar a busca em profundidade no grafo G' realizando a busca a partir do vértice de maior t[u] obtido na linha 1.
- Se a busca em profundidade não alcançar todos os vértices, inicie uma nova busca em profundidade a partir do vértice de maior t[u] dentre os vértices restantes.
- Retornar os vértices de cada árvore da floresta obtida na busca em profundidade na linha 3 como um componente fortemente conectado separado.