Вершины, рёбра, степени. Матрица смежности и список смежности. Canvas-редактор.
Граф — пара (V, E), где V — множество вершин, E — множество рёбер между ними. Простая модель, описывающая связи: соцсети, карты, схемы зависимостей.
Логические схемы состоят из элементов и связей между ними. Если забыть про электрические сигналы и оставить только «что с чем соединено» — получится граф! Вершины — это элементы (И, ИЛИ, НЕ), рёбра — провода между ними. Так глава 16 неявно готовила вас к понятию графа: любая схема — частный случай графа, только ориентированного и чаще всего без циклов. Графы — универсальный язык для описания любых связей: дороги между городами, друзья в соцсетях, зависимости задач в проекте.
Вершины — пользователи, рёбра — дружба. Связь двусторонняя.
Вершины — города, веса — расстояния. Найти кратчайший путь.
Папки — вершины, файлы — листья. Иерархия вложенности.
Что должно быть сделано до начала следующей задачи.
Связь двусторонняя. Дружба в соцсети, дороги.
Связь односторонняя. Подписки, односторонние дороги.
Каждому ребру — число (длина, стоимость, время).
V вершин, V−1 рёбер, между любыми двумя вершинами ровно один путь.
Каждая пара вершин соединена. K_n: n(n−1)/2 рёбер.
Рёбра только между группами. Соцсеть (авторы ↔ посты).
A[i][j] = 1, если есть ребро i→j, иначе 0. Для неориентированного A симметрична.
Занимает O(N²) памяти. Быстро проверять наличие ребра O(1).
Рёбра: (A,B), (A,C), (B,D), (C,D)
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 1 | 0 | 0 | 1 |
| C | 1 | 0 | 0 | 1 |
| D | 0 | 1 | 1 | 0 |
Кликни по холсту — добавь вершину. Зажми на вершине и потяни к другой — создай ребро.
Введи матрицу смежности: 1 = есть ребро, * = вес/длина, 0 = нет ребра. Граф построится автоматически.
| A | B | C | D | |
|---|---|---|---|---|
| A | ||||
| B | ||||
| C | ||||
| D |