Таблица и граф для одного объекта
💻 Информатика · 6 класс
Два способа представить данные
Одни и те же сведения можно записать по-разному. Часто связи между объектами представляют либо таблицей, либо графом. Это две разные информационные модели одних и тех же данных. Выбор способа зависит от того, какой вопрос мы хотим решать быстрее и какая запись нагляднее в конкретной задаче.
Таблица — это строки и столбцы, где на пересечении записано значение. Граф — это вершины-объекты и рёбра-связи между ними. И таблица, и граф хранят одинаковые сведения, просто показывают их по-разному.
Пример: дороги между городами
Пусть есть три города и известно, какие из них соединены дорогой. Запишем это таблицей, где «да» означает наличие прямой дороги между городами.
| Город А | Город Б | Город В | |
|---|---|---|---|
| Город А | — | да | нет |
| Город Б | да | — | да |
| Город В | нет | да | — |
Те же данные в виде графа: вершины — это города, рёбра — дороги между ними.
А — Б — В (А и В напрямую не соединены)Когда что удобнее
Таблица и граф хранят одинаковые сведения, но подходят для разных задач. Зная их сильные стороны, легко выбрать нужный способ.
- таблица удобна, когда нужно быстро проверить одну связь по строке и столбцу;
- граф удобен, когда нужно увидеть всю картину связей сразу;
- по таблице легко вести подсчёты, по графу — наглядно искать путь;
- при большом числе объектов таблица занимает меньше места, чем запутанный граф.
Переход между моделями
Из таблицы можно построить граф и наоборот, ничего не теряя. При переходе от таблицы к графу проводят ребро там, где в клетке стоит «да». При обратном переходе сначала рисуют пустую таблицу с теми же объектами, а затем по каждому ребру ставят «да» в нужную клетку. После перехода стоит проверить себя: число рёбер в графе должно совпасть с числом клеток «да» в таблице.
Заметим, что в таблице связей клетки по двум сторонам от диагонали повторяют друг друга, ведь дорога между А и Б — это та же дорога, что между Б и А. Поэтому такую таблицу достаточно заполнить наполовину, а в графе это всего одно ребро.
Какой способ выбрать
Чёткого правила, что всегда лучше, нет: всё зависит от задачи. Если в вопросе спрашивают про конкретную пару объектов, быстрее заглянуть в таблицу. Если же нужно проследить цепочку связей или найти дорогу из одного города в другой через промежуточные, нагляднее граф. Опытный человек умеет легко переходить от одной модели к другой и выбирает ту, что удобнее именно сейчас.
Правило: переходя от таблицы к графу, проводят ребро там, где в таблице стоит «да». При обратном переходе заполняют клетки по рёбрам графа. Сами данные при этом не меняются — меняется лишь форма записи.
Кратко о главном
- Связи между объектами можно записать таблицей или графом.
- Это две модели одних и тех же данных.
- Таблица удобна для проверки и подсчётов, граф — для поиска путей.
- Переход между ними не меняет самих данных.