Aceasta e o versiune anterioară a paginii.
Un graf neorientat este o pereche ordonată de multimi(X,U),unde:
Un graf are următoarele elemente:
Având lista de adiacentă:
Se numeşte lanţ elementar un lanţ în care nu se repetă vârfuri.
Un graf orientat este o pereche ordonată de mulțimi G={X,U},unde:
poza
Matricea de adiacență - este o matrice a cu n linii și n coloane,în care elementele a[i,j] se definesc astfel:
Matricea vârfuri-arce este o matrice B cu n = |X| linii și m = |U| coloane,în care fiecare element b[i,j] este:
Parcurgerea în lățime (Breadth-First-Search -BFS) este o metodă ce presupune vizitarea nodurilor în următoarea ordine:
Pe masură ce algoritmul avansează,se colorează nodurile în felul următor:
Se păstrează informațiile despre distanța până la nodul sursă. Se obține arborele BFS
Pentru implementarea BFS se utilizează o coadă (Q) în care inițial se află doar nodul sursă.Se vizitează pe rând vecinii acestui nod și se pun și ei în coadă.În momentul în care nu mai există vecini nevizitați,nodul sursă este scos din coadă.
Pentru fiecare nod u din graf { culoare[u]=alb d[u] = infinit //in d se retine distanta pana la nodul sursa p[u] = null // } culoare[sursă]=gri d[sursă]=0 enqueue(Q,sursă) //punem nodul sursă în coada Q Cât timp coada Q nu este vidă { v=dequeue(Q) //extragem nodul v din coadă pentru fiecare u dintre vecinii lui v dacă culoare[u] == alb { culoare[u] = gri p[u] = v d[u] = d[v] + 1 enqueue(Q,u) //adăugăm nodul u în coadă } culoare[v] = negru //am terminat explorarea vecinilor lui v }
Parcurgea în adâncime (Depth-First-Search -DFS) presupune explorarea nodurilor în următoarea ordine:
Această metoda de parcurgere pune prioritate pe explorarea în adâncime (pe distanțe tot mai mari față de nodul sursă).