Algoritmo de búsqueda en profundidad (DFS)

Tabla de contenido

Algoritmo de búsqueda de profundidad primero
Ejemplo de búsqueda de profundidad primero
Pseudocódigo DFS (implementación recursiva)
Implementación de DFS en Python, Java y C / C ++
Complejidad de la búsqueda de profundidad primero
Aplicación del algoritmo DFS

En este tutorial, aprenderá sobre el algoritmo de búsqueda en profundidad con ejemplos y pseudocódigo. Además, aprenderá a implementar DFS en C, Java, Python y C ++.

Profundidad primero Búsqueda o Profundidad primer recorrido es un algoritmo recursivo para buscar todos los vértices de un gráfico o estructura de datos de árbol. Recorrer significa visitar todos los nodos de un gráfico.

Algoritmo de búsqueda de profundidad primero

Una implementación estándar de DFS coloca cada vértice del gráfico en una de dos categorías:

Visitó
No visitado

El propósito del algoritmo es marcar cada vértice como visitado evitando ciclos.

El algoritmo DFS funciona de la siguiente manera:

Empiece por poner cualquiera de los vértices del gráfico encima de una pila.
Tome el elemento superior de la pila y agréguelo a la lista de visitas.
Cree una lista de los nodos adyacentes de ese vértice. Agregue los que no están en la lista de visitas a la parte superior de la pila.
Siga repitiendo los pasos 2 y 3 hasta que la pila esté vacía.

Ejemplo de búsqueda de profundidad primero

Veamos cómo funciona el algoritmo Depth First Search con un ejemplo. Usamos un gráfico no dirigido con 5 vértices.

Gráfico no dirigido con 5 vértices

Partimos del vértice 0, el algoritmo DFS comienza poniéndolo en la lista de Visitas y poniendo todos sus vértices adyacentes en la pila.

Visite el elemento y colóquelo en la lista de visitados

A continuación, visitamos el elemento en la parte superior de la pila, es decir, 1 y vamos a sus nodos adyacentes. Como ya se ha visitado 0, visitamos 2 en su lugar.

Visite el elemento en la parte superior de la pila

El vértice 2 tiene un vértice adyacente no visitado en 4, por lo que lo agregamos a la parte superior de la pila y lo visitamos.

Después de visitar el último elemento 3, no tiene nodos adyacentes no visitados, por lo que hemos completado el primer recorrido de profundidad del gráfico.

Pseudocódigo DFS (implementación recursiva)

El pseudocódigo para DFS se muestra a continuación. En la función init (), observe que ejecutamos la función DFS en cada nodo. Esto se debe a que el gráfico puede tener dos partes desconectadas diferentes, por lo que para asegurarnos de cubrir todos los vértices, también podemos ejecutar el algoritmo DFS en cada nodo.

 DFS (G, u) u.visited = verdadero para cada v ∈ G.Adj (u) if v.visited == false DFS (G, v) init () (Para cada u ∈ G u.visited = falso Para cada u ∈ G DFS (G, u))

Implementación de DFS en Python, Java y C / C ++

El código para el algoritmo de búsqueda en profundidad primero con un ejemplo se muestra a continuación. El código se ha simplificado para que podamos centrarnos en el algoritmo en lugar de otros detalles.

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