Luați în considerare algoritmul pentru identificarea tuturor ciclurilor elementare într-un grafic neorientat. Acest articol va descrie algoritmul și punerea sa în limbajul de programare C #.
Un ciclu într-un grafic este un lanț finit, care începe și se termină în același vertex. Ciclul secvență nodurile notate pe care le conține, de exemplu: (3-5-6-7-3).
Apropo, despre lanțul, în special căutare circuite elementare în coloana am scris recent.
Ciclul se numește elementar. în cazul în care toate nodurile incluse în ea sunt diferite (cu excepția inițială și finală).
Să ne uităm la un exemplu. Să presupunem că avem un grafic:
Enumerați toate ciclurile elementare în ea: 2-3-4-2, 2-3-5-4-2, 3-2-4-3, 3-2-4-5-3, 3-4-5-3 , 4-3-2-4, 4-3-5-4, 4-2-3-5-4, 5-4-3-5, 5-4-2-3-5.
Să presupunem că graficul este dat ca G = (V, E). unde V - un set de noduri ale grafului și E - mulțimea muchiilor grafului. Vârfurile și marginile reprezintă obiecte de astfel de clase:
Luați în considerare de lucru DFScycle algoritm. La momentul inițial toate nodurile de culoare alba. Trebuie să faceți următoarele:
Bucla prin toate nodurile, fiecare dintre ele poate avea un ciclu elementar. vopsi toate nodurile în alb la fiecare iterație (notat cu 1, iar culoarea neagră va fi notat cu 2). Adăugați la lista ciclului de vârfuri de vârf ciclului curent.
Acum să vorbim despre opțiunea unavailableEdge. Top, în căutarea unui ciclu, vopsi în negru nu va, altfel programul nu va fi capabil să se întoarcă la ea, pentru că acest nod devine indisponibil. Prin urmare, vom introduce variabila unavailableEdge, care va transmite numărul ultimei coaste, la care tranziția între vârfurile, respectiv, această margine la pasul următor ar fi disponibil pentru tranziția. De fapt, este necesar doar la primul nivel de recursie, pentru a evita funcționarea incorectă a algoritmului și de ieșire, de exemplu, rezultă o căutare eronată 1-2-1 în cazul în care există un astfel de grafic:
Procedura DFScycle apel (...).