Algoritmi/Algoritmi kod neusmerenih grafova

Predstavljanje grafa

Prvo-u-dubinu

Pseudokod

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

Klasifikacija grana

Unakrsne grane

Postoje dobre tehnike od: Yogesh Jakhar

Pretraživanje u širinu

Pseudokod

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

Upotreba

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

Topološko sortiranje

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.