Содержание
- 2. Определения Связный граф – это граф, в котором существует цепь между каждой парой вершин. k-cвязный граф
- 3. Описание графа Матрица смежности – это матрица, элемент M[i][j] которой равен 1, если существует ребро из
- 4. Весовая матрица Весовая матрица – это матрица, элемент W[i,j] которой равен весу ребра из вершины i
- 5. Задача Прима-Краскала Задача: соединить N городов телефонной сетью так, чтобы длина телефонных линий была минимальная. Та
- 6. Жадный алгоритм Жадный алгоритм – это многошаговый алгоритм, в котором на каждом шаге принимается решение, лучшее
- 7. Реализация алгоритма Прима-Краскала Проблема: как проверить, что 1) ребро не выбрано, и 2) ребро не образует
- 8. Реализация алгоритма Прима-Краскала Структура «ребро»: type rebro = record i, j: integer; { номера вершин }
- 9. Реализация алгоритма Прима-Краскала for k:=1 to N-1 do begin min := MaxInt; for i:=1 to N
- 10. Сложность алгоритма Основной цикл: O(N3) for k:=1 to N-1 do begin ... for i:=1 to N
- 11. Кратчайшие пути (алгоритм Дейкстры) Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение.
- 12. Алгоритм Дейкстры
- 13. Реализация алгоритма Дейкстры Массивы: массив a, такой что a[i]=1, если вершина уже рассмотрена, и a[i]=0, если
- 14. Реализация алгоритма Дейкстры Основной цикл: если все вершины рассмотрены, то стоп. среди всех нерассмотренных вершин (a[i]=0)
- 15. Реализация алгоритма Дейкстры Шаг 2: Шаг 3:
- 16. Как вывести маршрут? Результат работа алгоритма Дейкстры: длины путей Маршрут из вершины 0 в вершину 4:
- 17. Алгоритм Флойда-Уоршелла Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение. Найти все
- 18. Алгоритм Флойда-Уоршелла Версия с запоминанием маршрута: for i:= 1 to N for j := 1 to
- 19. Задача коммивояжера Задача коммивояжера. Коммивояжер (бродячий торговец) должен выйти из первого города и, посетив по разу
- 21. Скачать презентацию