![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
for k =1 to | V | do
for i =1 to | V | do
for j =1 to | V | do
aijaij Ú aik Ù akj
Упражнения:
1.Заметим, что в алгоритме 2, основанном на выражении 5.1, элементы матрицы А ( k -1) непосредственно преобразуются в элементы матрицы А ( k ), то есть не используется дополнительная память для хранения элементов матрицы А ( k -1). Докажите, что такая реализация выражения 5.1 корректна.
2. Очевидно, что трудоемкость алгоритма нахождения транзитивного замыкания O(| V |3). Представьте строки матрицы А в битовой форме и снизьте трудоемкость алгоритма до O(| V |2). Реализуйте оба варианта алгоритма и сравните время их работы.
3. Реализуйте алгоритм нахождения матрицы достижимости на основе использования стратегии поиска в глубину или ширину и сравните время работы этого алгоритма с временем работы алгоритма нахождения транзитивного замыкания.
4. Доработайте алгоритм нахождения транзитивного замыкания таким образом, чтобы в случае достижимости вершины j из вершины i сохранялась информация о пути, по которому j достижима из i.
Указание. Для хранения путей используйте матрицу P размера n ´ n, где n – число вершин графа. Элементы матрицы можно определить одним из двух способов:
1) Pij – вершина, предшествующая вершине j на пути из вершины i в вершину j;
2) Pij – вершина, следующая за вершиной i на пути из вершины i в вершину j.
Дата публикования: 2015-01-04; Прочитано: 364 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!