Please enable JavaScript.
Coggle requires JavaScript to display documents.
DFS & BFS, Toposort - Coggle Diagram
DFS & BFS
DFS
Depth-First Search ou Busca por Profundidade é um algoritmo que começa em um vértice arbitrário de um grafo e o marca visitado.
A cada iteração, o algoritmo prossegue para cada vértice não visitado que é adjacente para o que ele está. Se existem vários desses vértices, o vértice que vai ser visitado em seguida é ditado pela estrutura de dados que guarda o grafo.
Tal processo se repete até um "dead-end", ou seja, o momento em que não existe um próximo vértice não visitado a se visitar. Quando isso acontece, o algoritmo "volta' até um vértice que ainda possui vértices adjacentes a serem visitados.
Desse modo, conseguimos visitar todos os vértices do mesmo componente conectado do vértice inicial.
Usamos uma stack para fazer DFS, ou simplesmente fazer uma recursão. DFS é muito útil quando queremos construir uma foresta DFS
Análise de eficiência
O tempo é proporcional ao tamanho da estrutura de dados utilizada para representar o grafo. Em uma matriz de adjacência a eficiência é (-) (V²) (theta) em que V é o número de vértices.
Enquanto para uma lista de adjacência é (-) (V+E) em que E é o número de arestas.
-
BFS
Breadth-First Search ou Busca em Largura também é utilizada para visitar todos os vértices de um grafo, marcando-os como visitado, mas utiliza uma queue para traçar a sua operação.
-
Possui a mesma eficiência temporal da DFS e também possui dois tipos de arestas em sua floresta, além de também ser utilizada para checar a conectividade ou aciclicidade de um grafo.
-
São dois algoritmos utilizados para atravessar um grafo, são "buscas exaustivas"
Toposort
Topological Sorting é um problema em grafos em que queremos uma certa ordem de vértices em um digrafo arbitrário. Para toposort ser possível, o digrafo deve ser um DAG.
Para checar se um grafo é um DAG, podemos performar uma DFS e tomar nota da ordem em que os vértices se tornam "dead-ends". Reverter essa ordem é a solução do toposort desde que nenhuma back edge tenha sido encontrada.
Também podemos fazer um toposort implementando uma técnica de Diminuir-Para-Conquistar, repetidamente identificando no digrafo uma fonte, ou seja, um vértice com grau de entrada 0 e o delete junto com suas arestas. A ordem em que os vértices são deletados é uma solução pro toposort.
DAG
Se uma floresta DFS de um digrafo não possui nenhuma back edge, então o grafo é um grafo direcionado e acíclico (DAG)
-