Please enable JavaScript.
Coggle requires JavaScript to display documents.
Graph Traversal Algorithms - Coggle Diagram
Graph Traversal Algorithms
Breadth-First Search (BFS)
Processo
Marca todos os vértices como "não visitados"
Para cada vértice não visitado, chama bfs(v)
Marca o vértice com um contador e insere na fila
Atravessa todos os vértices adjacentes não visitados e os adiciona à fila
BFS Forest
Raiz de cada árvore é o vértice inicial
Arestas de árvore conectam vértices na primeira visita
Arestas cruzadas conectam vértices em níveis iguais ou adjacentes
Aplicações
Verificar conectividade
Verificar aciclicidade
Encontrar caminhos com o menor número de arestas
Eficiência
Matriz de adjacência: O(|V|^2)
Lista de adjacência: O(|V| + |E|)
Definição
Inicia a partir de um vértice arbitrário e marca-o como visitado
Visita todos os vértices adjacentes primeiro, depois os vértices a duas arestas de distância, e assim por diante
Utiliza uma fila para rastrear o percurso
Depth-First Search (DFS)
Definição
Inicia a partir de um vértice arbitrário e marca-o como visitado
Visita recursivamente vértices adjacentes não visitados
Utiliza uma pilha para rastrear o percurso
Processo
Marca todos os vértices como "não visitados"
Para cada vértice não visitado, chama dfs(v)
Marca o vértice com um contador
Atravessa todos os vértices adjacentes não visitados recursivamente
DFS forest
Raiz de cada árvore é o vértice inicial
Arestas de árvore conectam vértices na primeira visita
Arestas de retorno conectam um vértice a um ancestral não imediato
Aplicações
Verificar conectividade
Verificar aciclicidade
Identificar componentes conectados
Articulação de pontos
Eficiência
Matriz de adjacência: O(|V|^2)
Lista de adjacência: O(|V| + |E|)
Exhaustive Search
DFS (Depth-First Search)
BFS (Breadth-First Search)
Comparação entre DFS e BFS
Estrutura de dados
DFS: Pilha
BFS: Fila
Tipos de arestas (grafos não direcionados)
DFS: Arestas de árvore e de retorno
BFS: Arestas de árvore e cruzadas
Número de ordenações de vértices
DFS: Duas ordenações
BFS: Uma ordenação
Aplicações
DFS: Conectividade, aciclicidade, pontos de articulação
BFS: Conectividade, aciclicidade, caminhos mínimos
Eficiência
Matriz de adjacência: O(|V|^2) para ambos
Lista de adjacência: O(|V| + |E|) para ambos