A SZÉLESSÉGI FAVÁZ KERESÉSÉNEK (= II. ELJÁRÁS) SZÁMÍTÓGÉPES MEGVALÓSÍTÁSÁRÓL

A II. eljárásban adott algoritmus végrehajtásához szükségünk van annak adminisztrálására, hogy melyek azok a pontok, amelyekkel már végeztünk, (amelyeknek már összes szomszédját megkerestük), és melyek a „vizsgálat alatt levő” pontok, azaz azok, amelyek már sorra kerültek mint szomszédok (mint fiúk), de még nem kerestük meg a szomszédaikat (a fiaikat). Az előbbi egyszerűen megoldható, amennyiben minden pontot megindexelünk. Kezdetben minden index 0, és ha egy pontot vizsgálat alá veszünk, indexét –1-re változtatjuk, ha pedig végeztünk vele, indexét 1-re változtatjuk. Nem 0 indexű pontokat nem veszünk hozzá újra a favázhoz, sem a “vizsgálat alatt levő” pontokhoz. Viszont a –1 indexű pontokat külön tárolni célszerű, mégpedig úgy, hogy mindig hozzáférjünk a legrégebben tárolt ponthoz, és azt könnyen el tudjuk hagyni, ha már végeztünk vele.

Nyilvánvaló, hogy ha a II. eljárást megvalósító, most leírt algoritmus egy nem 0 indexű ponthoz ér, akkor a gráfban kört talált. A gráf pontosan akkor körmentes, ha ez az algoritmus sosem ér újra nem 0 indexű ponthoz.

Ha kipróbáljuk konkrét gráfokon, akkor jól látható, hogy a II. eljárás alapos, körültekintő, „megfontolva haladó” algoritmus: a kiinduló pont „környezetét” járja végig táguló körökben.

MEGJEGYZÉS:

Megjegyezzük, hogy a szélességi faváz „polinomiális időben” megtalálható, ami azt jelenti, hogy van olyan p(n) polinom, hogy bármely n pontú gráf szélességi favázának megtalálásához elég p(n) idő.

TARTALOMJEGYZÉK