Gradivo za takmičenje u Gimnaziji "Veljko Petrović"

Računarstvo i Informatika

Grafovi

Povezanost grafa

Ako pustimo DFS prodeduru iz čvora b, niz Idx će izgledati (2, 1, 3, 4, 5, 0, 0, 0) iz čega se vidi da neki čvorovi nisu posećeni. Tj, posećeni su samo oni ćvorovi koji se nalaze u istoj komponenti povezanosti u kojoj je i polazni čvor.

Da bismo posetili sve čvorove u grafu, moramo pustiti DFS iz svih čvorova koji nisu posećeni prethodnim pozivom DFS-a. Sledeći kod opisuje posetu svih čvorova u grafu bez obzira na to kojoj komponenti povezanosti pripadaju. Idx, Lbl i G su globalne promenljive.

Procedure FullDFS(v : TCvor);
Begin
  DFS(v)
  For v := 1 to g.N do
      if Idx[v] = 0 then DFS(v);
End;

Kada znamo kako radi DFS, možemo lako proveriti da li je neki graf povezan. Jednostavno pustimo DFS iz prvog čvora, i pogledamo u Idx ima li koja nula. Ako ima, znači da graf nije povezan.

Valid XHTML 1.0 Strict! | Site map | Kontakt | © 2007..2015 prof. Duško Obradović sa učenicima Gimnazije