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: Есть ли требования к порядку вершин в списке «всех вершин, соединенных с данной вершиной» в списке смежности?
Порядок может быть произвольным. Но на практике может понадобиться сортировка по определенному правилу, например по порядку добавления вершин или по возрастанию значений вершин. Это помогает быстро находить вершины с некоторым экстремальным свойством.