Графы и деревья
💻 Информатика · 5 класс
Что такое граф
Иногда удобно показать не сами объекты, а связи между ними. Для этого используют граф. Граф — это схема, в которой объекты обозначены точками, а связи между ними — линиями. Точки называют вершинами, а линии — рёбрами.
Зачем нужны графы
Графом удобно изобразить дороги между городами, друзей в классе или схему метро. По графу легко увидеть, какие объекты связаны напрямую, а какие — только через другие.
- Вершина — объект (город, человек, станция).
- Ребро — связь между двумя объектами (дорога, дружба, перегон).
- Путь — цепочка рёбер, по которой можно пройти от одной вершины к другой.
Что такое дерево
Дерево — это особый граф, который похож на перевёрнутое дерево. У него есть главная вершина — корень, от неё идут ветви к другим вершинам. В дереве от корня к любой вершине ведёт только один путь, и в нём нет замкнутых колец.
Деревом удобно показывать то, что разделяется на части: состав семьи, разделы книги, папки в компьютере.
| Понятие | Что обозначает | Пример |
|---|---|---|
| Вершина | Объект | Город |
| Ребро | Связь | Дорога между городами |
| Корень | Главная вершина дерева | Папка верхнего уровня |
Разбор примера
Покажем деревом папки на компьютере:
Компьютер
├ Документы
│ ├ Школа
│ └ Рисунки
└ Игры
Здесь «Компьютер» — корень, от него ветви идут к папкам «Документы» и «Игры», а от «Документов» — к «Школе» и «Рисункам».
Где встречаются графы и деревья
Графы и деревья окружают нас в самых разных местах, хотя мы не всегда называем их этими словами. Карта дорог между городами — это граф: города являются вершинами, а дороги между ними — рёбрами. Схема метро тоже граф: станции — вершины, перегоны между соседними станциями — рёбра. По такому графу пассажир ищет путь от своей станции до нужной, пересчитывая перегоны и пересадки.
Деревья применяют там, где целое делится на части, а части — на ещё меньшие части. Папки в компьютере вложены друг в друга и образуют дерево. Оглавление книги — тоже дерево: книга делится на главы, главы — на разделы. Родословная семьи изображается деревом, поэтому её так и называют — генеалогическое дерево.
| Где применяется | Что вершины | Что рёбра |
|---|---|---|
| Карта дорог | Города | Дороги |
| Схема метро | Станции | Перегоны |
| Папки на диске | Папки и файлы | Вложенность |
Как найти путь по графу
Чтобы пройти от одной вершины к другой, двигаются по рёбрам, переходя из вершины в вершину. Цепочку таких переходов называют путём. Между двумя вершинами может быть несколько путей или не быть ни одного, если они не связаны. Самый короткий путь — тот, в котором меньше всего рёбер.
Частая ошибка. В дереве не должно быть замкнутых колец из рёбер. Если из вершины можно вернуться в неё же по разным рёбрам, это уже не дерево, а граф с циклом.
Кратко о главном
- Граф — это схема из вершин (объектов) и рёбер (связей).
- По графу удобно искать пути между объектами.
- Дерево — граф без замкнутых колец с одной главной вершиной — корнем.
- Деревья применяют для папок, разделов книг и других вложенных структур.