IPRJ – PROJETO E ANÁLISE DE ALGORITMOS
LISTA DE EXERCÍCIOS 09
1) Considerando o seguinte grafo:
a) Implemente o algoritmo de Prim para encontrar uma árvore geradora mínima.
b) Implemente o algoritmo de Kruskal para encontrar uma árvore geradora mínima.
É permitido utilizar implementações auxiliares de Heap e Disjoint Sets. Exemplos:
Heap:
C++: http://www.cplusplus.com/reference/queue/priority_queue/
Java: http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html
C#: https://visualstudiomagazine.com/Articles/2012/11/01/Priority-Queues-with-C.aspx
Disjoint Sets:
C++ e C# - http://web.rememberingemil.org/Projects/DisjointSets.aspx.html
Java: http://git.eclipse.org/c/platform/eclipse.platform.ui.git/plain/bundles/org.eclipse.ui.ide/
src/org/eclipse/ui/internal/ide/misc/DisjointSet.java
Java: http://www.cs.waikato.ac.nz/~bernhard/317/source/graph/UnionFind.java