Algoritmos em Grafos

• Busca
• Menor Caminho
• Árvore Geradora Mínima

Busca

• A Busca em Largura (BFS – Breadth-First Search) – Esse algoritmo realiza uma busca em um grafo explorando os nós de um grafo em níveis. O algoritmo utiliza uma filapara explorar o grafo.

• Busca em Profundidade (DFS – Depth-First Search) – Esse algoritmo realiza uma busca em um grafo explorando todos os nós de um ramo, antes de considerar nós em um próximo ramo do grafo. O algoritmo utiliza uma pilha para explorar o grafo.

Menor Caminho

• Algoritmo de Dijkstra – Essa algoritmo encontra o caminho mais curto entre dois nós em um grafo ponderado, mantendo um conjunto de nós não visitados e suas respectivas distâncias estimadas até o nó de origem. A cada passo, o algoritmo processa o nó não visitado que tenha a menor distância estimada até o nó de destino e atualiza as distâncias estimadas.

Árvore Geradora Mínima

• Algoritmo de Prim – Esse algoritmo encontra a árvore geradora mínima em um grafo não direcionado e ponderado adicionando nós à árvore geradora mínima um a um, até que todos os possível nós tenham sido incluídos na sub-árvore.