Часть 3-2с. 1. Написать на С программу, которая вводит данные взвешенного графа число вершин
 Скачать 159.17 Kb.
|
|
1. Написать на С++ программу, которая: – вводит данные взвешенного графа (число вершин n, матрицу расстояний M, затем вводит номер начальной вершины а, конечной b; – вычисляет в массиве R кратчайшее расстояние от вершины а до b; – выводит это расстояние и вершины пути из а до b. Вывести формулу трудоемкости этого алгоритма для графа из n вершин и m ребер. 2. Написать на С++ программу, которая: – вводит данные неориентированного графа (число вершин n, число ребер m, ребра, как пары номеров вершин); – формирует матрицу смежности графа; – вычисляет принадлежность вершин компонентам связности просмотром вширь; – выводит результат в виде: количество компонент, номера вершин 1-й компоненты с максимальным числом вершин, номера вершин 2-й компоненты с максимальным среди оставшихся компонент числом вершин и т.д. Вывести формулу трудоемкости этого алгоритма для графа из n вершин и m ребер. |