Содержание
- 2. Структуры данных Структуры данных Составитель курса лекций: Спиричева Наталия Рахматулловна, ст. преподаватель каф. Информационных технологий
- 3. Спиричева Н.Р. ГРАФЫ
- 4. Структуры данных Структуры данных и алгоритмы Целью лекции является приобретение студентами следующих компетенций: знать методы представления
- 5. Структуры данных Структуры данных и алгоритмы Основные темы лекции: Понятие древовидных структур Деревья Графы Алгоритмы поиска
- 6. Спиричева Н.Р. Первая работа по теории графов, принадлежит известному швейцарскому математику Л. Эйлеру. В 1736 г.
- 7. Спиричева Н.Р. Несколько модифицируем задачу. Каждую из рассматриваемых местностей, разделенных рекой, обозначим точкой, а соединяющие их
- 8. Спиричева Н.Р. Предположим, что футбольная команда вашей школы участвует в соревнованиях и играет с командами других
- 9. Спиричева Н.Р. Схема такого вида называется графом. Она состоит из нескольких точек А, В, С, D.
- 10. Структуры данных Введение Сетевые структуры – весьма общий и гибкий класс связных списков.
- 11. Структуры данных Введение Дерево - конечное множество, состоящее из одного или более элементов, называемых узлами. Корень
- 12. Структуры данных Введение Определим дерево как конечное множество Т, состоящее из одного или более узлов, таких,
- 13. Структуры данных Из определения следует: Каждый узел дерева является корнем некоторого поддерева, которое содержится в этом
- 14. Структуры данных Введение Обычно дерево представляется в машинной памяти в форме многосвязного списка, в котором каждый
- 15. Структуры данных Введение Сетевые структуры – весьма общий и гибкий класс связных списков.
- 16. Спиричева Н.Р. Дерево
- 17. Спиричева Н.Р. Свойства деревьев 1. Любая пара вершин соединена единственным маршрутом. 2. Количество ребер меньше на
- 18. Спиричева Н.Р. Рассмотрим произвольное дерево.Для того чтобы построить дерево, выберем какую нибудь вершину А0 Из А0
- 19. Структуры данных Дерево – структура данных, представляющая собой древовидную структуру в виде набора связанных узлов. Бинарное
- 20. Структуры данных Бинарное дерево Бинарное дерево - конечное множество узлов, которое является пустым или состоит из
- 21. Структуры данных Бинарное дерево В алгоритмах работы с древовидными структурами наиболее часто встречается понятие обход дерева.
- 22. Структуры данных Бинарное дерево Прямой порядок обхода: Попасть в корень Пройти левое поддерево Пройти правое поддерево
- 23. Структуры данных Бинарное дерево “Прошитые” деревья В “прошитых” деревьях концевые связи-указатели используются для связи с родителями,
- 24. Структуры данных ЛЕС Лес – это множество (обычно упорядоченное), состоящее из некоторого (быть может равного нулю)
- 25. Структуры данных Графы Граф - некоторое множество точек (называемых вершинами) и некоторое множество линий (называемых ребрами),
- 26. Структуры данных Графы Граф - некоторое множество точек (называемых вершинами) и некоторое множество линий (называемых ребрами),
- 27. Спиричева Н.Р. Важным при рассмотрении графов является вопрос о том, какие графы можно и нужно считать
- 28. Спиричева Н.Р. Для многих целей безразлично, как именно изображен граф, т. е. изоморфные графы, доставляющие одну
- 29. Структуры данных Графы Каждая пара вершин в графе соединяется не больше чем одним ребром. Дуга, соединенная
- 30. Структуры данных Графы Пусть V и V` - вершины и пусть n≥0; говорят, что «V0, V1,
- 31. Структуры данных Графы Граф называется связным, если имеется путь между каждыми двумя вершинами этого графа. Циклом
- 32. Структуры данных Степень входа вершины – количество входящих в нее ребер, степень выхода – количество исходящих
- 33. Структуры данных Графы
- 34. Структуры данных Графы Задание графа: Класс матриц инциденции. Если граф Г содержит n вершин и m
- 35. Структуры данных Графы
- 36. Структуры данных Графы Класс матриц смежности. Матрица смежности S=[sij]nxm невзвешенного графа определяется следующим образом: Во взвешенном
- 37. Структуры данных Графы
- 38. Спиричева Н.Р. Раскраски В теории графов, раскраска графов является частным случаем разметки графов. При раскраске элементам
- 39. Спиричева Н.Р. Каждый многоугольный граф можно представить себе как некоторую географическую карту, где грани- это страны,
- 40. Спиричева Н.Р. Когда говорят о раскраске графов, почти всегда подразумевают под этим раскраску их вершин, то
- 41. Спиричева Н.Р. В теории графов рёберной раскраской графа называется назначение «цветов» рёбрам графа таким образом, что
- 42. Спиричева Н.Р. Граф-цикл может быть раскрашен в два цвета если длина цикла чётна — просто используем
- 43. Спиричева Н.Р. В теории графов тотальной раскраской называется вид раскраски вершин и рёбер графа. Если не
- 44. Структуры данных Алгоритмы поиска путей в графе Путь с минимальным количеством промежуточных вершин Алгоритм просматривает вершины
- 45. Структуры данных Волновой алгоритм Каждой вершине i приписывается два целых числа Times[i] - временная метка и
- 46. Структуры данных Под корректностью алгоритма здесь понимается, что: алгоритм завершает работу за конечное время; если решение
- 47. Структуры данных Алгоритмы поиска путей в графе Путь минимальной суммарной длины во взвешенном графе с неотрицательными
- 48. Структуры данных Алгоритмы поиска путей в графе Алгоритм, по которому происходит поиск, заключается в следующем: всем
- 49. Структуры данных Алгоритмы поиска путей в графе Алгоритм Дейкстры (пример) Пусть требуется найти расстояния от 1-й
- 50. Структуры данных Алгоритмы поиска путей в графе Алгоритм Дейкстры (пример) Кружками обозначены вершины, линиями — пути
- 51. Структуры данных Алгоритмы поиска путей в графе Алгоритм Дейкстры (пример) Первый шаг. Рассмотрим шаг алгоритма Дейкстры
- 52. Структуры данных Алгоритмы поиска путей в графе Алгоритм Дейкстры (пример) Первый по очереди сосед вершины 1
- 53. Структуры данных Алгоритмы поиска путей в графе Алгоритм Дейкстры (пример) Аналогичную операцию проделываем с двумя другими
- 54. Структуры данных Алгоритмы поиска путей в графе Алгоритм Дейкстры (пример) Все соседи вершины 1 проверены. Текущее
- 55. Структуры данных Алгоритмы поиска путей в графе Алгоритм Дейкстры (пример) Второй шаг. Шаг алгоритма повторяется. Снова
- 56. Структуры данных Алгоритмы поиска путей в графе Алгоритм Дейкстры (пример) Снова пытаемся уменьшить метки соседей выбранной
- 57. Структуры данных Алгоритмы поиска путей в графе Алгоритм Дейкстры (пример) Ещё один сосед вершины 2 —
- 58. Структуры данных Алгоритмы поиска путей в графе Алгоритм Дейкстры (пример) Все соседи вершины 2 просмотрены, замораживаем
- 59. Структуры данных Алгоритмы поиска путей в графе Алгоритм Дейкстры (пример) Третий шаг. Повторяем шаг алгоритма, выбрав
- 60. Структуры данных Алгоритмы поиска путей в графе Алгоритм Дейкстры (пример) Дальнейшие шаги. Повторяем шаг алгоритма для
- 61. Структуры данных Алгоритмы поиска путей в графе Путь минимальной суммарной длины во взвешенном графе с произвольными
- 62. Структуры данных Алгоритмы поиска путей в графе Нахождение K путей минимальной суммарной длины во взвешенном графе
- 63. Структуры данных Алгоритмы поиска путей в графе Алгоритм: 1. Найти минимальный путь P1=(v11,...,v1L[1]). Положить k =
- 64. Структуры данных 1.Какими структурами данных можно представить в памяти древовидные структуры? 2. Перечислите основные алгоритмы поиска
- 66. Скачать презентацию