„Programozás/Algoritmusok” változatai közötti eltérés
Tartalom törölve Tartalom hozzáadva
→Szélességi keresés algoritmusa √: komment pontosítás |
→Mélységi keresés algoritmusa √: komment |
||
771. sor:
::még nem bejárt pont
<pre>
int idő; //globális változó, ezzel számoljuk hogy mennyit mozogunk a gráfban
void MélyKeres(Graf G) { //inicializálás
d[1..G.size()]; //érkezési idő
f[1..G.size()]; //elhagyási idő
apa[1..G.size()] = 0; //a pontok apját tároló tömb ki nullázása
idő = 0; //inicializálás vége
for(p: G.V) if(!apa[p]) { //végig lépked a gráfban lévő fák gyökrein
apa[p] = -1; //feljegyzi az apa tömbben hogy gyökerek
MélyBejár(G, p); //bejárja a gyökerekhez tartozó fákat
}
}
void MélyBejár(Graf G, int u) {
d[u] = ++idő; //növeli eggyel az időt, majd tárolja a ponthoz az érkezési táblán
for (v: G[u].ki) if(!apa[v]) { //kiválasztja sorba a pont fiait, és ha nem lett még bejárva bejárja öket sorban
apa[v] = u; //feljegyzi az apa táblán v fiuhoz hogy u az apja
MélyBejár(G, v); //rekurzivan meghívja magát v-re amíg be nem járja a részfát
}
f[u] = ++idő; //feljegyzi az elhagyási időt, ekkora u összes részfája be lett járva
}
</pre>
| |||