9.4 Краткие итоги¶
1. Основные моменты¶
- Граф состоит из вершин и ребер и может быть задан как множество вершин и множество ребер.
- По сравнению с линейными отношениями (связный список) и отношениями разделения (дерево), сетевые отношения (граф) обладают большей свободой и потому более сложны.
- Ребра ориентированного графа имеют направление, в связном графе любые вершины достижимы друг из друга, а в взвешенном графе каждое ребро несет переменную веса.
- Матрица смежности использует матрицу для представления графа: каждая строка и каждый столбец соответствуют вершине, а элементы матрицы показывают, есть между двумя вершинами ребро или нет. Матрица смежности очень эффективна для операций добавления, удаления, поиска и изменения, но расходует больше памяти.
- Список смежности использует несколько списков для представления графа; \(i\)-й список соответствует вершине \(i\) и хранит все ее смежные вершины. По сравнению с матрицей смежности список смежности экономит пространство, но для поиска ребра в нем приходится обходить список, поэтому по времени он уступает.
- Когда списки в списке смежности становятся слишком длинными, их можно преобразовать в красно-черное дерево или хеш-таблицу, чтобы ускорить поиск.
- С точки зрения алгоритмической идеи матрица смежности отражает принцип "обмен пространства на время", а список смежности - принцип "обмена времени на пространство".
- Графы можно использовать для моделирования различных реальных систем, таких как социальные сети, линии метро и так далее.
- Дерево является частным случаем графа, а обход дерева - частным случаем обхода графа.
- Обход графа в ширину представляет собой способ поиска, который расширяется от ближнего к дальнему и обычно реализуется с помощью очереди.
- Обход графа в глубину представляет собой способ поиска, который сначала идет до самого конца, а затем возвращается назад, когда путь исчерпан; обычно он реализуется на основе рекурсии.
2. Q & A¶
Q: Что считается путем: последовательность вершин или последовательность ребер?
Определение в разных языковых версиях Википедии различается: в английской версии путь определяется как "последовательность ребер", а в китайской версии - как "последовательность вершин". В английской версии исходная формулировка выглядит так: In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices.
В этой книге путь рассматривается как последовательность ребер, а не как последовательность вершин. Причина в том, что между двумя вершинами может существовать несколько ребер, и в таком случае каждому ребру соответствует свой путь.
Q: Есть ли в несвязном графе вершины, до которых нельзя дойти?
В несвязном графе, начиная из некоторой вершины, по крайней мере одна вершина оказывается недостижимой. Чтобы обойти весь несвязный граф, нужно задать несколько стартовых точек и обойти все связные компоненты графа.
Q: Есть ли требования к порядку вершин в списке "всех вершин, соединенных с данной вершиной" в списке смежности?
Порядок может быть произвольным. Но на практике может понадобиться сортировка по определенному правилу, например по порядку добавления вершин или по возрастанию значений вершин; это помогает быстро находить вершины с некоторым экстремальным свойством.