Algoritmi/Algoritmi kod neusmerenih grafova

Izvor: Викикњиге
Idi na navigaciju Idi na pretragu

Predstavljanje grafa[uredi]

Susedstvo matrica[uredi]

Susedstvo listi[uredi]

Poređenje[uredi]

Prvo-u-dubinu[uredi]

Pseudokod[uredi]

 dfs(vertex w)
   if w has already been marked visited
     return
   mark w as visited
   for each adjacent vertex v
     dfs(v)

Osobine[uredi]

Klasifikacija grana[uredi]

Grane stabla[uredi]

Grane koje idu unazad[uredi]

Grane koje idu unapred[uredi]

Unakrsne grane[uredi]

Postoje dobre tehnike od: Yogesh Jakhar

Pretraživanje u širinu[uredi]

Pseudokod[uredi]

bfs ( x ):

 q insert x;
 while (q not empty )
    y = remove head  q
    visit y
    mark y
    for each z adjacent y 
      q add tail z

Primer[uredi]

Tačnost[uredi]

Analize[uredi]

Upotreba[uredi]

Pretraživanje u širinu se može koristiti u istraživanju šema baza podataka, sa namerom da se pretvori u xml šemu. Ovo se ostvaruje tako što imenujemo korenu tabelu i onda uradimo referentno pretraživanje u širinu. Pretraživanje je obavljeno i referentnim krajevima, tako da ako neka druga tabela ponudi trenutnom čvoru da se pretraži,onda ta tabela ima jedan-do-mnogo odnosa u xml šemi, inače je mnogo-do-jednog.

Klasični problemi kod grafa[uredi]

Topološko sortiranje[uredi]

A topological sort is an ordering of vertices in a directed acyclic graph such that if there is a path from vi to vj, then vj appears after vi in the ordering.

Topološko sortiranje je određivanje redosleda čvorova u direktnom acikličnom grafu tako da ako postoji put od čvora vi do čvora vj, onda se čvor vj pojavljuje posle čvora vi u redosledu.

Dat je graf G. Topološko sortiranje može biti predstavljeno sa sledećim koracima.

  1. Pronaći bilo koji čvor bez ulaznih grana i ubaciti ga u listu
  2. Ukloniti ga zajedno sa svojim granama (Sve grane bi trebalo da budu izlazne)
  3. Ponoviti korak 1 dok nema više čvorova
  4. Alternativa je da koristite prvo-u-dubinu obrnutim kasnijim redosledom. Ovo znači darekurzivno ubacite čvor nakon posećivanja njegove dece u listi i obrnuti listu. Ovo radi induktivno, jer najdublje dete nema svoje dete i biće prvo ubačeno u listu. Onda njegovi roditelji, pa roditelji njegovih roditelja itd.

Topološko sortiranje je korisno kada je računanje osobina dece, koja zavise od istih osobina roditelja, kao rastojanje od početnog čvora. Ovo dozvoljava traženje najkraće putanje do ciljnog čvora.

Jako povezane komponente[uredi]

Artikulacija čvora[uredi]

Most[uredi]

Prečnik[uredi]