Algoritam dubinskog pretraživanja (DFS)

U ovom vodiču naučit ćete o algoritmu pretraživanja dubine s primjerima i pseudokodom. Također, naučit ćete implementirati DFS na C, Java, Python i C ++.

Dubinsko prvo pretraživanje ili Dubinsko prvo prevrtanje je rekurzivni algoritam za pretraživanje svih vrhova strukture podataka grafa ili stabla. Prelazak znači posjećivanje svih čvorova grafa.

Dubina algoritma prvog pretraživanja

Standardna DFS implementacija stavlja svaki vrh grafa u jednu od dvije kategorije:

  1. Posjećeno
  2. Nije posjećeno

Svrha algoritma je označiti svaki vrh kao posjećen uz izbjegavanje ciklusa.

DFS algoritam radi na sljedeći način:

  1. Započnite stavljanjem bilo kojeg od vrhova grafa na vrh stoga.
  2. Uzmite gornju stavku stoga i dodajte je na posjećeni popis.
  3. Stvorite popis susjednih čvorova tog vrha. Na vrh snopa dodajte one koji nisu na posjećenom popisu.
  4. Ponavljajte korake 2 i 3 dok se stog ne isprazni.

Primjer dubinskog pretraživanja

Pogledajmo kako algoritam dubinskog pretraživanja radi na primjeru. Koristimo neusmjereni graf s 5 vrhova.

Neusmjereni graf s 5 vrhova

Polazimo od vrha 0, DFS algoritam započinje stavljanjem na popis Posjećeno i stavljanjem svih susjednih vrhova u stog.

Posjetite element i stavite ga na popis posjećenih

Dalje, posjetimo element na vrhu stoga, tj. 1 i idemo do njegovih susjednih čvorova. Budući da je 0 već posjećeno, umjesto njih posjetimo 2.

Posjetite element na vrhu stoga

Vertex 2 ima ne posjećeni susjedni vrh u 4, pa ga dodamo na vrh stoga i posjetimo ga.

Vertex 2 ima ne posjećeni susjedni vrh u 4, pa ga dodamo na vrh stoga i posjetimo ga. Vertex 2 ima ne posjećeni susjedni vrh u 4, pa ga dodamo na vrh stoga i posjetimo ga.

Nakon što posjetimo posljednji element 3, on nema nijedan ne posjećen susjedni čvor, pa smo dovršili dubinsko prelaženje grafa.

Nakon što posjetimo posljednji element 3, on nema nijedan ne posjećen susjedni čvor, pa smo dovršili dubinsko prelaženje grafa.

DFS pseudokod (rekurzivna implementacija)

Pseudokod za DFS prikazan je u nastavku. U funkciji init () primijetite da pokrećemo funkciju DFS na svakom čvoru. To je zato što graf može imati dva različita odvojena dijela, pa kako bismo bili sigurni da pokrivamo svaki vrh, također možemo pokrenuti DFS algoritam na svakom čvoru.

 DFS (G, u) u.visited = true za svaki v ∈ G.Adj (u) ako je v.visited == false DFS (G, v) init () (Za svaki u ∈ G u.visited = false Za svaki u ∈ G DFS (G, u))

Implementacija DFS-a u Python, Java i C / C ++

Kôd algoritma dubinskog pretraživanja s primjerom prikazan je u nastavku. Kôd je pojednostavljen tako da se možemo usredotočiti na algoritam, a ne na druge pojedinosti.

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; )

Složenost dubinskog pretraživanja

Složenost vremena algoritma DFS predstavljena je u obliku O(V + E), gdje Vje broj čvorova i Ebroj bridova.

Složenost prostora algoritma je O(V).

Primjena DFS algoritma

  1. Za pronalaženje puta
  2. Da bi se ispitalo je li graf dvostrani
  3. Za pronalaženje jako povezanih komponenata grafa
  4. Za otkrivanje ciklusa u grafu

Zanimljivi članci...