9.3. Összefüggő komponensek

Az ÖSSZEFÜGGŐ -KOMPONENSEK programmal egy G gráf összefüggő komponenseit határozhatjuk meg. A program elve a következő: kezdetben minden egyes csúcshoz készítünk egy diszjunkt halmazt, majd sorban az összes élre egyesítjük a végpontokhoz tartozó halmazokat. Mire az élek végére jutunk, elkészülnek a komponensek is. Tekintsük az algoritmus futását a 9.3.1. ábrán látható gráfra! Az 1. táblázatban láthatóak a program futása során generált diszjunkt halmazok. Az összefüggő komponenseket a táblázat utolsó sorában található halmazok adják meg.

Procedure ÖSSZEFÜGGő-KOMPONENSEK(G) 
Input: G gráf 
Eredmény: meghatározza a G gráf komponenseit 
1 forall the v ∊ V do 
2    HALMAZT-KÉSZÍT(v) 
3 endfall
4 forall the (u, v) ∊ E do 
5    if HALMAZT-KERES(u) != HALMAZT-KERES(v) then 
6       EGYESÍT(u,v) 
7    endif
8 endfall 

9.3. ábra - 9.3.1. ábra. Példagráf összefüggő komponensek meghatározásához

9.3.1. ábra. Példagráf összefüggő komponensek meghatározásához

9.4. ábra - 1. táblázat. A kiszámolt komponensek

1. táblázat. A kiszámolt komponensek