Neste tutorial, você aprenderá sobre o algoritmo de pesquisa em profundidade com exemplos e pseudocódigo. Além disso, você aprenderá a implementar DFS em C, Java, Python e C ++.
Pesquisa de profundidade primeiro ou passagem de profundidade primeiro é um algoritmo recursivo para pesquisar todos os vértices de um gráfico ou estrutura de dados em árvore. Traversal significa visitar todos os nós de um gráfico.
Algoritmo de primeira pesquisa de profundidade
Uma implementação DFS padrão coloca cada vértice do gráfico em uma de duas categorias:
- Visitou
- Não visitou
O objetivo do algoritmo é marcar cada vértice como visitado, evitando ciclos.
O algoritmo DFS funciona da seguinte maneira:
- Comece colocando qualquer um dos vértices do gráfico no topo de uma pilha.
- Pegue o item do topo da pilha e adicione-o à lista de visitados.
- Crie uma lista dos nós adjacentes desse vértice. Adicione aqueles que não estão na lista de visitados no topo da pilha.
- Continue repetindo as etapas 2 e 3 até que a pilha esteja vazia.
Exemplo de primeira pesquisa de profundidade
Vamos ver como o algoritmo de pesquisa de profundidade primeiro funciona com um exemplo. Usamos um gráfico não direcionado com 5 vértices.
Gráfico não direcionado com 5 vértices
Começamos no vértice 0, o algoritmo DFS começa colocando-o na lista Visitada e colocando todos os seus vértices adjacentes na pilha.
Visite o elemento e coloque-o na lista de visitados
Em seguida, visitamos o elemento no topo da pilha, ou seja, 1 e vamos para seus nós adjacentes. Como 0 já foi visitado, visitamos 2 em seu lugar.
Visite o elemento no topo da pilha
O vértice 2 tem um vértice adjacente não visitado em 4, portanto, adicionamos esse vértice ao topo da pilha e o visitamos.
O vértice 2 tem um vértice adjacente não visitado em 4, então o adicionamos ao topo da pilha e o visitamos. 
O vértice 2 tem um vértice adjacente não visitado em 4, então o adicionamos ao topo da pilha e o visitamos.
Depois de visitar o último elemento 3, ele não tem nenhum nó adjacente não visitado, portanto, concluímos a primeira travessia de profundidade do gráfico.
Depois de visitar o último elemento 3, ele não tem nenhum nó adjacente não visitado, portanto, concluímos a primeira travessia de profundidade do gráfico.
Pseudocódigo DFS (implementação recursiva)
O pseudocódigo para DFS é mostrado abaixo. Na função init (), observe que executamos a função DFS em cada nó. Isso ocorre porque o gráfico pode ter duas partes desconectadas diferentes, portanto, para garantir que cobriremos todos os vértices, também podemos executar o algoritmo DFS em cada nó.
DFS (G, u) u.visited = true para cada v ∈ G.Adj (u) se v.visited == false DFS (G, v) init () (Para cada u ∈ G u.visited = false Para cada u ∈ G DFS (G, u))
Implementação DFS em Python, Java e C / C ++
O código para o algoritmo de primeira pesquisa de profundidade com um exemplo é mostrado abaixo. O código foi simplificado para que possamos nos concentrar no algoritmo em vez de outros detalhes.
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; )
Complexidade da primeira pesquisa de profundidade
A complexidade de tempo do algoritmo DFS é representada na forma de O(V + E), onde Vé o número de nós e Eé o número de arestas.
A complexidade espacial do algoritmo é O(V).
Aplicação do Algoritmo DFS
- Para encontrar o caminho
- Para testar se o gráfico é bipartido
- Para encontrar os componentes fortemente conectados de um gráfico
- Para detectar ciclos em um gráfico
