hello-algo/ru/docs/chapter_graph/summary.md

Резюме

Основные моменты

• Граф состоит из вершин и ребер и может быть представлен как множество вершин и множество ребер.
• По сравнению с линейными отношениями (список) и отношениями разделения (дерево), сетевые отношения (граф) обладают большей свободой и, следовательно, являются более сложными.
• В ориентированном графе ребра имеют направление, в связном графе любая вершина достижима, во взвешенном графе каждое ребро содержит переменную веса.
• Матрица смежности использует матрицу для представления графа, где каждая строка (столбец) соответствует вершине, элементы матрицы представляют ребра, используя 1 или 0 для обозначения наличия или отсутствия ребра между двумя вершинами. Матрица смежности очень эффективна в операциях добавления, удаления, поиска и изменения, но требует значительных затрат памяти.
• Список смежности использует несколько связных списков для представления графа, где $i$-й список соответствует вершине i и содержит все смежные вершины этой вершины. Список смежности более экономичен по памяти по сравнению с матрицей смежности, но менее эффективен по времени, так как требуется просматривать список для поиска ребра.
• Когда связный список в списке смежности становится слишком длинным, его можно преобразовать в красно-черное дерево или хеш-таблицу для повышения эффективности поиска.
• С точки зрения алгоритмического подхода, матрица смежности воплощает принцип "обмена пространства на время", а список смежности воплощает принцип "обмена времени на пространство".
• Графы можно использовать для моделирования различных реальных систем, таких как социальные сети, линии метро и т. д.
• Дерево является частным случаем графа, обход дерева также является частным случаем обхода графа.
• Обход графа в ширину — это метод поиска, который расширяется слой за слоем от ближайших к дальним вершинам, обычно реализуется с помощью очереди.
• Обход графа в глубину — это метод поиска, который идет до конца, а затем возвращается назад, когда дальше идти некуда, часто реализуется на основе рекурсии.

Вопросы и ответы

В: Путь — это последовательность вершин или последовательность ребер?

В разных языковых версиях Википедии определения различаются: в английской версии "путь — это последовательность ребер", а в китайской версии "путь — это последовательность вершин". Вот оригинальный текст из английской версии: In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices.

В данном тексте путь рассматривается как последовательность ребер, а не последовательность вершин. Это связано с тем, что между двумя вершинами может существовать несколько ребер, и каждое ребро соответствует отдельному пути.

В: Будут ли в несвязном графе вершины, которые невозможно обойти?

В несвязном графе, начиная с определенной вершины, существует по крайней мере одна вершина, которую невозможно достичь. Для обхода несвязного графа необходимо установить несколько начальных точек, чтобы обойти все связные компоненты графа.

В: В списке смежности должен ли быть определенный порядок "всех вершин, соединенных с данной вершиной"?

Порядок может быть произвольным. Однако в практических приложениях может потребоваться сортировка по определенным правилам, например, в порядке добавления вершин или в порядке возрастания значений вершин и т. д., что помогает быстро находить вершины "с определенным экстремальным значением".