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
Parcurgerea grafurilor in latime
-
A_Cristian
- guru
- Mesaje: 1975
- Membru din: 23 Feb 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.
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.