Keresés elemi ciklus a grafikonon - programozás C, C # és java
Tekintsük azt az algoritmust találni az összes elemi ciklus egy irányítatlan gráf. Ez a cikk leírja az algoritmus és annak végrehajtását a C # programozási nyelv.
Egy ciklus egy gráf egy véges lánc, amely kezdődik és végződik ugyanabban az vertex. Ciklus jelöljük csúcsokat szekvenciát, amely tartalmaz, például: (3-5-6-7-3).
By the way, a láncban, nevezetesen keresni elemi áramkörök oszlopban írtunk a közelmúltban.
A ciklus az úgynevezett elemi. Ha minden csomópont benne foglalt különböző (kivéve a kezdeti és a végső).
Nézzünk egy példát. Tegyük fel, hogy adott egy gráf:
Felsorolni az összes elemi ciklus benne: 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.
Tegyük fel, a gráf adja meg: G = (V, E). ahol V - egy sor a gráf, és E - a élek halmazát a gráf. A csúcsok és az élek képviseli tárgyak ilyen osztályok:
Törekedjen DFScycle algoritmus. A kezdeti időben az összes csúcsot fehér színű. Meg kell csinálni a következő:
Végigjárjuk az összes csúcsot, ezek mindegyike képes egy elemi ciklus. Frissít minden csúcs fehér mindegyik ismétlésnél (jelölése 1, és a fekete szín lesz jelöljük 2). Add, hogy a lista csúcsok ciklus aktuális ciklus csúcsa.
Most beszéljünk a lehetőséget unavailableEdge. Top, keres egy ciklus átfestés fekete nem, különben a program nem tud visszatérni, mert ez a csomópont elérhetetlenné válik. Ezért bevezetni változó unavailableEdge, amely utóbbi továbbítja a számát az utolsó borda, amelynél az átmenetet a csúcsok, illetve ez az él a következő lépés az lenne elérhetetlenné az átmenet. Valójában ez csak akkor szükséges, az első szinten rekurzió, hogy ne helytelen működése az algoritmus és kimenet, például egy hibás keresési eredmények 1-2-1 ha van ilyen grafikon:
DFScycle eljárás kezdeményezése (...).