|
Titlul: Ciclu in graf Scris de: Parfene Narcis din Februarie 05, 2015, 15:28:05 V-as ruga sa-mi dati si mie cateva indicatii la urmatoarea problema:
Se da un graf neorientat si un nod x din acest graf. Sa se verifice daca exista un ciclu care trece prin x si in caz ca exista sa se afiseze. Ma intereseaza o solutie de complexitate polinomiala. Multumesc. Titlul: Răspuns: Ciclu in graf Scris de: Alexandru Valeanu din Februarie 05, 2015, 16:53:27 Faci o parcurgere (DFS/BFS) din nodul X si daca la un moment dat ajungi intr-un nod Y si muchia (Y,X) exista, ai un ciclu si printezi drumul de la X la Y. Trebui sa ai grija si prin ce muchie ajungi in Y.
|