Ebben az oktatóanyagban megismerheti az első keresési algoritmus példáit és álkódját. Ezenkívül megtanulja megvalósítani a DFS-t C, Java, Python és C ++ nyelven.
A Mélység első keresése vagy a Mélység első bejárása rekurzív algoritmus a grafikon vagy fa adatszerkezet összes csúcsának keresésére. A bejárás azt jelenti, hogy meglátogatja a gráf összes csomópontját.
Mélység első keresési algoritmus
A szokásos DFS megvalósítás a grafikon minden csúcsát a két kategória egyikébe sorolja:
- Meglátogatott
- Nincs meglátogatva
Az algoritmus célja, hogy minden csúcsot meglátogatottként jelöljön meg, miközben elkerüli a ciklusokat.
A DFS algoritmus a következőképpen működik:
- Kezdje azzal, hogy a gráf bármelyik csúcsát a verem tetejére helyezi.
- Vegyük a verem legfelső elemét, és adjuk hozzá a meglátogatott listához.
- Hozzon létre egy listát a csúcs szomszédos csomópontjairól. Adja hozzá azokat, amelyek nem szerepelnek a felkeresett listában, a verem tetejére.
- 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
Nézzük meg, hogyan működik a Depth First Search algoritmus egy példával. 5 irányú irányítatlan grafikont használunk.
Irányítatlan gráf 5 csúccsal
A 0 csúcsból indulunk ki, a DFS algoritmus azzal kezdődik, hogy a Visited listába teszi, és az összes szomszédos csúcsát a verembe rakja.
Látogassa meg az elemet, és tegye be a meglátogatott listába
Ezután meglátogatjuk a verem tetején lévő elemet, azaz 1, és megyünk a szomszédos csomópontokhoz. Mivel a 0 már meglátogatott, helyette 2-et látogatunk meg.
Látogassa meg a verem tetején található elemet
A 2. csúcsnak van egy meglátogatatlan szomszédos csúcsa a 4-ben, ezért hozzáadjuk ezt a verem tetejéhez, és meglátogatjuk.
A 2. csúcsnak van egy meglátogatatlan szomszédos csúcsa a 4-ben, ezért hozzáadjuk a verem tetejéhez, és meglátogatjuk. 
A 2. csúcsnak van egy meglátogatatlan szomszédos csúcsa a 4-ben, ezért hozzáadjuk ezt a verem tetejéhez, és meglátogatjuk.
Miután meglátogattuk az utolsó 3 elemet, nincsenek meglátogatatlan szomszédos csomópontjai, ezért befejeztük a grafikon Első mélységi átjárását.
Miután meglátogattuk az utolsó 3 elemet, nincsenek meglátogatatlan szomszédos csomópontjai, ezért befejeztük a grafikon Első mélységi átjárását.
DFS álkód (rekurzív megvalósítás)
A DFS álkódját az alábbiakban mutatjuk be. Az init () függvényben vegye figyelembe, hogy minden csomóponton futtatjuk a DFS függvényt. Ennek oka, hogy a grafikonnak két különálló, leválasztott része lehet, így annak biztosítása érdekében, hogy minden csúcsot lefedjünk, minden csomóponton futtathatjuk a DFS algoritmust is.
DFS (G, u) u.visited = igaz minden v ∈ G.Adj (u) ha v.visited == hamis DFS (G, v) init () (mindegyik u u ∈ G DFS (G, u))
DFS megvalósítás Pythonban, Java-ban és C / C ++ verzióban
Az alábbiakban bemutatjuk a Mélység első keresési algoritmus kódját egy példával. A kódot leegyszerűsítettük, hogy más részletek helyett az algoritmusra koncentrálhassunk.
Python Java C C + # DFS algorithm in Python # DFS algorithm def dfs(graph, start, visited=None): if visited is None: visited = set() visited.add(start) print(start) for next in graph(start) - visited: dfs(graph, next, visited) return visited graph = ('0': set(('1', '2')), '1': set(('0', '3', '4')), '2': set(('0')), '3': set(('1')), '4': set(('2', '3'))) dfs(graph, '0')
// DFS algorithm in Java import java.util.*; class Graph ( private LinkedList adjLists(); private boolean visited(); // Graph creation Graph(int vertices) ( adjLists = new LinkedList(vertices); visited = new boolean(vertices); for (int i = 0; i < vertices; i++) adjLists(i) = new LinkedList(); ) // Add edges void addEdge(int src, int dest) ( adjLists(src).add(dest); ) // DFS algorithm void DFS(int vertex) ( visited(vertex) = true; System.out.print(vertex + " "); Iterator ite = adjLists(vertex).listIterator(); while (ite.hasNext()) ( int adj = ite.next(); if (!visited(adj)) DFS(adj); ) ) public static void main(String args()) ( Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 3); System.out.println("Following is Depth First Traversal"); g.DFS(2); ) )
// DFS algorithm in C #include #include struct node ( int vertex; struct node* next; ); struct node* createNode(int v); struct Graph ( int numVertices; int* visited; // We need int** to store a two dimensional array. // Similary, we need struct node** to store an array of Linked lists struct node** adjLists; ); // DFS algo void DFS(struct Graph* graph, int vertex) ( struct node* adjList = graph->adjLists(vertex); struct node* temp = adjList; graph->visited(vertex) = 1; printf("Visited %d ", vertex); while (temp != NULL) ( int connectedVertex = temp->vertex; if (graph->visited(connectedVertex) == 0) ( DFS(graph, connectedVertex); ) temp = temp->next; ) ) // Create a node struct node* createNode(int v) ( struct node* newNode = malloc(sizeof(struct node)); newNode->vertex = v; newNode->next = NULL; return newNode; ) // Create graph struct Graph* createGraph(int vertices) ( struct Graph* graph = malloc(sizeof(struct Graph)); graph->numVertices = vertices; graph->adjLists = malloc(vertices * sizeof(struct node*)); graph->visited = malloc(vertices * sizeof(int)); int i; for (i = 0; i adjLists(i) = NULL; graph->visited(i) = 0; ) return graph; ) // Add edge void addEdge(struct Graph* graph, int src, int dest) ( // Add edge from src to dest struct node* newNode = createNode(dest); newNode->next = graph->adjLists(src); graph->adjLists(src) = newNode; // Add edge from dest to src newNode = createNode(src); newNode->next = graph->adjLists(dest); graph->adjLists(dest) = newNode; ) // Print the graph void printGraph(struct Graph* graph) ( int v; for (v = 0; v numVertices; v++) ( struct node* temp = graph->adjLists(v); printf(" Adjacency list of vertex %d ", v); while (temp) ( printf("%d -> ", temp->vertex); temp = temp->next; ) printf(""); ) ) int main() ( struct Graph* graph = createGraph(4); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 2); addEdge(graph, 2, 3); printGraph(graph); DFS(graph, 2); return 0; )
// DFS algorithm in C++ #include #include using namespace std; class Graph ( int numVertices; list *adjLists; bool *visited; public: Graph(int V); void addEdge(int src, int dest); void DFS(int vertex); ); // Initialize graph Graph::Graph(int vertices) ( numVertices = vertices; adjLists = new list(vertices); visited = new bool(vertices); ) // Add edges void Graph::addEdge(int src, int dest) ( adjLists(src).push_front(dest); ) // DFS algorithm void Graph::DFS(int vertex) ( visited(vertex) = true; list adjList = adjLists(vertex); cout << vertex << " "; list::iterator i; for (i = adjList.begin(); i != adjList.end(); ++i) if (!visited(*i)) DFS(*i); ) int main() ( Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 3); g.DFS(2); return 0; )
A mélység első keresésének összetettsége
A DFS algoritmus időbeli bonyolultsága a következő formában van ábrázolva: O(V + E)ahol Va csomópontok Eszáma és az élek száma.
Az algoritmus térbeli összetettsége az O(V).
A DFS algoritmus alkalmazása
- Az út megtalálásáért
- Annak tesztelésére, hogy a grafikon kétoldalas-e
- A grafikon erősen összekapcsolt komponenseinek megkereséséhez
- A ciklusok detektálására egy grafikonon
