Mélység első Keresést, vagy Mélység első útját egy rekurzív algoritmus keresni a csúcsok egy grafikon, vagy fa struktúra. A keresztirányú azt jelenti, hogy meglátogatjuk a grafikon összes csomópontját.

> Mélysége Első Keresési Algoritmus

normál DFS végrehajtását teszi minden csúcsának a grafikon a két kategóriák:

1. Látogatott
2. Nem Látogatott

A cél az algoritmus, hogy mark minden csúcsának, mint látogatott, miközben elkerüli a ciklus.,

a DFS algoritmus a következőképpen működik:

1. Kezdje azzal, hogy a grafikon csúcsait egy köteg tetejére helyezi.
2. vegye fel a köteg felső elemét, majd adja hozzá a meglátogatott listához.
3. hozzon létre egy listát a vertex szomszédos csomópontjairól. Adja hozzá azokat, amelyek nem szerepelnek a meglátogatott listában a verem tetejére.
4. addig ismételje a 2.és a 3. lépést, amíg a verem kiürül.

mélység első Keresési példa

lássuk, hogyan működik a mélység első Keresési algoritmusa egy példával. Egy irányítatlan gráfot használunk 5 csúcsokkal.,

a vertex 0-ból indulunk, a DFS algoritmus úgy kezdődik, hogy a meglátogatott listába helyezi, és az összes szomszédos csúcsot a verembe helyezi.

ezután meglátogatjuk a verem tetején található elemet, azaz 1, és menjünk a szomszédos csomópontokhoz. Mivel a 0-t már meglátogatták, helyette 2-t látogatunk meg.,

Vertex 2 van egy nem látogatott szomszédos Vertex 4, így hozzá, hogy a tetején a verem, majd látogasson el.

miután meglátogattuk az utolsó 3 elemet, nem rendelkezik látogatatlan szomszédos csomópontokkal, így befejeztük a gráf első mélységét.,

DFS Pseudocode (rekurzív implementáció)

a DFS pszeudokódja az alábbiakban látható. Az init() függvényben vegye figyelembe, hogy minden csomóponton futtatjuk a DFS funkciót. Ennek oka az, hogy a grafikonnak két különböző leválasztott része lehet, így annak biztosítása érdekében, hogy minden csúcsot lefedjünk, a DFS algoritmust minden csomóponton futtathatjuk.,

DFS(G, u) u.visited = true for each v ∈ G.Adj if v.visited == false DFS(G,v) init() { For each u ∈ G u.visited = false For each u ∈ G DFS(G, u)}

DFS implementáció Python, Java és C/C++

a mélység első Keresési algoritmusának kódja egy példával az alábbiakban látható. A kód egyszerűsödött, így tudunk összpontosítani az algoritmus helyett más részleteket.

A mélység összetettsége első keresés

a DFS algoritmus idő összetettsége O(V + E), ahol V a csomópontok száma és E az élek száma.

az algoritmus térösszetétele O(V).,

DFS algoritmus alkalmazása

1. A
2. útvonal megtalálásához annak tesztelésére, hogy a grafikon kétpárti-e
3. egy gráf erősen összekapcsolt összetevőinek megtalálásához
4. a gráf ciklusainak kimutatására