PARCURGEREA GRAFURILOR NEORIENTATE

ObiectiveNoiuni teoretice despre parcurgeri (semnificaie, mod de realizare, scop);Metode de parcurgere;Parcurgerea n lime (prezentarea metodei, exemple);Algoritmul BF.

END

Parcurgere (noiuni teoretice)

Semnificaie: examinarea n mod sistematic a nodurilor unui graf;Realizare: se pleac dintr-un nod dat i, astfel nct fiecare nod accesibil din i pe muchii incidente dou cte dou, s fie atins o singur dat.Alte expresii similare: vizitare, traversare.Scop: prelucrrii informaiilor asociate nodurilor;determinarea aranjrii lineare a nodurilor n vederea trecerii de la unul la altulObservaii: Presupunem c mulimea vrfurilor este X={1, 2, , n};Presupunem c ordinea vrfurilor este dat de relaia

Metode de parcurgereParcurgere n lime (Breadth First - BF)Parcurgerea n adncime (Depth First - DF)

Parcurgerea n lime Breadth First - BFSe viziteaz vrful iniial x, apoi vecinii acestuia, apoi vecinii nevizitai ai acestora, i aa mai departe.Exemplu:Pentru graful din figura urmtoare ordinea de parcurgere a nodurilor cu metoda BF, cnd se pleac din vrful 1 este urmtoarea:

215431,2,3,4,5.

Pentru acelai graf, dac se pleac din nodul iniial 5, ordinea de parcurgere n lime este urmtoarea: Dac se pleac din nodul 2, lista vrfurilor obinut n urma parcurgerii BF este urmtoarea: 215433.4,1,2,5,5,3.4,1,2,

Variabilele utilizate n elaborarea unui program a - matricea de adiacen asociat grafului;trecut -vector n care se trec n ordine nodurileparcurse;n - numrul de noduri din graf;m - numrul de muchii din graf;e1,e2 - extremitile muchiilor;i,j - contori;x nodul din care se pleac;u - variabil (contor) ce ine evidena numrului de noduri vizitate;pc - nodul ai crui vecini i cutm;sol - vectorul rezultat n urma parcurgerii (conine nodurile n ordinea vizitrii lor).

Vectorul trecut care are n componente este definit astfel:

Deoarece algoritmul conine dou cicluri imbricate: unul while (care se execut de cel mult n-1 ori) i unul for (care se execut de n ori) rezult c ordinul de complexitate al algoritmului este O(n2).

Aplicaie:Fie graful din figura de mai jos. Se cere s se realizeze parcurgerea n lime pornind pe rnd din nodurile: 1, 12, 4, 7, 8, 5 i 10.