DFS vs BFS e Algoritmo de Prim para MST

DFS vs BFS

Vantagens DFS:

• Simples de implementar.
• Precisa de pouca memória para armazenar.

Desvantagens DFS:

• Pode, às vezes, falhar ao encontrar a solução.
• Não garante que seja a melhor solução.
• Pode demorar muito para encontrar a solução.

Vantagens BFS:

• Garante que encontra a solução (se esta existir).
• Dependendo do problema, pode garantir que a solução encontrada é a melhor.

Desvantagens BFS:

• Mais complexo de implementar.
• Precisa de muita memória para armazenar.

Grafos: Minimum Spanning Tree (MST)

É um grafo ponderado. Uma árvore abrangente (spanning tree) de um grafo conexo é um subgrafo que contém todos os vértices do grafo e é uma árvore. A árvore abrangente de custo mínimo (MST) de um grafo conexo com V vértices é uma árvore constituída por V-1 arestas, que ligam todos os vértices do grafo e que tem o menor custo total possível.

• A árvore só existe se o grafo for conexo.
• É uma árvore porque é um grafo acíclico.
• É abrangente porque liga todos os vértices do grafo.
• É de custo mínimo porque o custo total das suas arestas é o menor custo possível.

Quando é inserida mais uma aresta, ele passa a ter um ciclo e deixa de ser uma árvore. Os custos das ligações podem ser negativos. Se houver custos iguais em ligações diferentes, a MST pode não ser única.

• Um corte num grafo: é uma partição dos vértices em dois conjuntos distintos.
• Uma ligação ponte (crossing edge): é uma ligação que une um vértice de um conjunto a um vértice de outro.

Algoritmo de Prim

Algoritmo ganancioso sendo recomendado para grafos densos. Este algoritmo é bom quando há muitos vértices. Baseia-se na ideia de manter um corte do grafo, dividindo-o em vértices pertencentes à MST e vértices não pertencentes à MST. Numa versão melhorada, pode ser considerado uma “extensão” do algoritmo de BFS (utiliza uma fila de espera com prioridades, em vez de uma fila de espera comum).

Eficácia:

Apresentado com uma Matriz de Adjacência:

• Com pesquisa baseada num vetor de pesos de ligações: O(V²) — eficaz para qualquer grafo denso (força bruta).
• Com pesquisa baseada em filas de espera com prioridades (através de heaps): O(E log V).
• Com pesquisa baseada em filas de espera com prioridades (através de uma heap Fibonacci): O(E + V log V). Não é eficaz em grafos densos, mas sim em muito densos.