Люди!!!!
Помогите плизззззз!!!!
У меня с графами не очень, а мне тут надо ответить на вопрос:

Нужно построить каркас в НЕВЗВЕШЕННОМ графе.
Какие из перечисленных алгоритмов могут это сделать и с какой сложностью?(перечислите все)

1. топологическая сортировка;
2. алгоритм Прима;
3. алгоритм Крускала;
4. алгоритм Форда-Фалкерсона;
5. алгоритм построения паросочетания в произвольном графе;
6. алгоритм Дейкстры;
7. алгоритм Форда-Беллмана;
8. алгоритм Флойда;
9. алгоритм обхода в ширину;
10. алгоритм обхода в глубину;
11. алгоритм построения эйлерова цикла;

Заранее благодарен.

Забежал к вам с sources.ru....
Вот:
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

Спасибо огромное