Komponenta souvislosti grafu je taková maximální podmnožina uzlů grafu, pro kterou platí, že mezi každými dvěma uzly vede sled.
Princip
Algoritmus pro zjištění počtu komponent je jednoduchou modifikací prohledávání do hloubky (DFS). Algoritmus nejprve označí veškeré uzly jako nenavštívené (FRESH) a uloží je do fronty. Poté pustí prohledávání do hloubky z prvního uzlu a zvýší počet nalazených komponent na 1. DFS pustupně projde všechny uzly dosažitelné z daného uzlu a po jejich zpracování je uzavře (stav CLOSED). Ve frontě jsou v tento okamžik stále označeny jako FRESH pouze ty uzly, které nepatřily do první komponenty. Algoritmus proto nalezne další uzel ve stavu FRESH, inrementuje počet nalezených komponent a zpracuje daný uzel pomocí DFS. Algoritmus terminuje v okamžiku, kdy už fronta neobsahuje žádný FRESH uzel.
Kód
/**
* Dosud neobjeveny uzel
*/
private static final int FRESH = 0;
/**
* Otevreny uzel
*/
private static final int OPENED = 1;
/**
* Uzavreny uzel
*/
private static final int CLOSED = 2;
/**
* Spocita pocet komponent neorientovaneho grafu
* @param graph graf
*/
public static int countComponents(GraphIface graph){
//Stavy jednotlivych uzlu
int[] state = new int[graph.getVertexCount()];
for(int i = 0; i < state.length; i++) state[i] = FRESH;
int counter = 0;
//zajisti pruchod vsemi komponentami souvislosti
for(int i = 0; i < graph.getVertexCount(); i++){
if(state[i] == FRESH){
counter++;
doDFS(graph, i, state);
}
}
return counter;
}
/**
* Provede prohledavani do hloubky
* @param graph graf
* @param vertexNr cislo uzlu
* @param state stavy uzlu
*/
private static void doDFS(GraphIface graph, int vertexNr, int[] state) {
state[vertexNr] = OPENED;
for(Integer i : graph.getEdges(vertexNr)){
if(state[i] == FRESH) doDFS(graph, i, state);
}
state[vertexNr] = CLOSED;
}