Вот:
1. топологическая сортировка - это про обход графа в определенном порядке - O(N^2)
2. алгоритм Прима - построение SST (Shortest Staining Tree - насчет второго слова не уверен, в общем - минимальное стягивающее дерево). Только тут про взвешанный граф. - O(N^2)
3. алгоритм Крускала - то же, что и для алгоритма Прима - O(N^2)
4. алгоритм Форда-Фалкерсона - максимальный поток в сети ~ O(N^3)
5. алгоритм построения паросочетания в произвольном графе - явно не каркас ~ O(N^3)
6. алгоритм Дейкстры - минимальное расстояние от вершины до всех остальных в графе с неотрицательными весами - O(N^2)
7. алгоритм Форда-Беллмана - минимальное расстояние между всеми вершинами с произвольными весами - O(N^3)
8. алгоритм Флойда (он же алгоритм Орщала-Флойда) - то же, что и Форд-Беллман, только в константу раз быстрее - O(N^3)
9. алгоритм обхода в ширину - DFS - это тоже не про каркас - O(N)
10. алгоритм обхода в глубину - BFS - аналогично - O(N)
11. алгоритм построения эйлерова цикла - опять же обход графа - O(N^2)
Получается, что только алгоритмы Прима и Круксала годятся для данной задачи. Если граф невзвешан, то эти алгоритмы можно использовать так: если ребро (i, j) есть, то его вес равен 1, иначе - машинной бесконечности.
Вообще, вот: http://pco.iis.nsk.su/~dyatlov/alg/graph/index.php
