Parcurgerea grafurilor in latime

Rezolvarea problemelor de matematica prin realizarea unor programe.
Melilo
utilizator
utilizator
Mesaje: 9
Membru din: 26 Oct 2015, 15:34

Parcurgerea grafurilor in latime

Mesaj de Melilo » 27 Oct 2015, 16:48

Intre n firme sunt stabilite relatii de colaborare (se cunosc perechile de firme care colaboreaza). Sa se determine lungimea minima a lantului de intermediari pentru ca firma x sa colaboreze cu firma y (program c++)

o idee macar
multumesc

A_Cristian
guru
guru
Mesaje: 1964
Membru din: 23 Feb 2015, 17:15

Mesaj de A_Cristian » 27 Oct 2015, 17:15

Tu vrei program sau algoritm?

In mare, algoritmul este cam asa:
- avem o lista de noduri, o notam L, pe care trebuie sa le vizitam. Populam lista cu nodul initial.
- parcurgem lista L si fie n nodul curent.
- fie V lista de noduri vecine a lui n. Daca exista noduri in V care nu se afla in L, adauga-le.
- conditia de oprire este in functie de cerinta problemei. In acest caz cand unul din nodurile puse in L este chiar y.

Exista mai multe moduri in care poti calcula distanta. Unul este sa faci o legatura inversa intre noduri. Alt mod este ca lista sa contina de fapt o pereche (nod, numar_pasi). Iar cand adaugi un nod la lista, numarul de pasi pana la noul nod este numarul de pasi pana la parinte + 1.

Scrie răspuns