Представление графов (матрица смежности, список смежности)

Материал из m6a
Перейти к: навигация, поиск

Граф — это абстрактная структура данных, представляющая собой множество вершин (узлов) и множество ребер, соединяющих эти вершины. Графы используются для моделирования различных систем и отношений между объектами, таких как социальные сети, транспортные сети, компьютерные сети и т.д. Существуют различные способы представления графов в памяти компьютера, наиболее распространенными из которых являются матрица смежности и список смежности.

Основные понятия

  1. Граф (Graph): Структура данных, состоящая из множества вершин (узлов) и множества ребер, соединяющих эти вершины.
  2. Вершина (Vertex): Узел графа.
  3. Ребро (Edge): Соединение между двумя вершинами графа.
  4. Матрица смежности (Adjacency Matrix): Двумерный массив, представляющий граф, где элемент (i, j) указывает на наличие или отсутствие ребра между вершинами i и j.
  5. Список смежности (Adjacency List): Список, где для каждой вершины графа хранится список смежных с ней вершин.
  6. Ориентированный граф (Directed Graph): Граф, в котором ребра имеют направление (от одной вершины к другой).
  7. Неориентированный граф (Undirected Graph): Граф, в котором ребра не имеют направления (связывают две вершины).
  8. Взвешенный граф (Weighted Graph): Граф, в котором каждому ребру присвоен вес (значение).

Матрица смежности (Adjacency Matrix)

Матрица смежности — это двумерный массив (матрица) размера $n \times n$, где $n$ — количество вершин в графе. Элемент матрицы $A[i][j]$ равен 1, если между вершинами $i$ и $j$ есть ребро, и 0, если ребра нет.

  1. Представление неориентированного графа: В неориентированном графе матрица смежности является симметричной, то есть $A[i][j] = A[j][i]$.
  2. Представление ориентированного графа: В ориентированном графе матрица смежности может быть несимметричной, то есть $A[i][j]$ может не быть равным $A[j][i]$.
  3. Представление взвешенного графа: Во взвешенном графе элемент матрицы $A[i][j]$ равен весу ребра между вершинами $i$ и $j$, если ребро существует, и некоторому специальному значению (например, $\infty$ или 0), если ребра нет.
  4. Преимущества:
    1. Простота реализации.
    2. Быстрая проверка наличия ребра между двумя вершинами (за время $O(1)$).
  5. Недостатки:
    1. Большой объем памяти, необходимый для хранения матрицы (пропорционален $n^2$).
    2. Неэффективность при работе с разреженными графами (графами, в которых количество ребер значительно меньше, чем $n^2$).
    3. Сложность добавления и удаления вершин (требуется изменение размера матрицы).

Пример представления неориентированного графа с использованием матрицы смежности (Python):

```python def adjacency_matrix(graph): 

   n = len(graph)
   matrix = [[0] * n for _ in range(n)]
   for i in range(n):
       for j in graph[i]:
           matrix[i][j] = 1
           matrix[j][i] = 1  # Для неориентированного графа
   return matrix
  1. Пример графа в виде списка смежности

graph = { 

   0: [1, 2],
   1: [0, 2, 3],
   2: [0, 1, 3],
   3: [1, 2]

}

matrix = adjacency_matrix(graph) for row in matrix: 

   print(row)

```

Вывод:

``` [0, 1, 1, 0] [1, 0, 1, 1] [1, 1, 0, 1] [0, 1, 1, 0] ```

Список смежности (Adjacency List)

Список смежности — это структура данных, представляющая граф в виде списка, где для каждой вершины графа хранится список смежных с ней вершин.

  1. Представление неориентированного графа: В неориентированном графе список смежности для каждой вершины содержит все вершины, с которыми она связана.
  2. Представление ориентированного графа: В ориентированном графе список смежности для каждой вершины содержит только те вершины, в которые есть ребро из данной вершины.
  3. Представление взвешенного графа: Во взвешенном графе в списке смежности для каждой вершины хранятся пары (соседняя вершина, вес ребра).
  4. Преимущества:
    1. Экономия памяти при работе с разреженными графами.
    2. Удобство добавления и удаления вершин и ребер.
  5. Недостатки:
    1. Более сложная реализация по сравнению с матрицей смежности.
    2. Более медленная проверка наличия ребра между двумя вершинами (за время $O(k)$, где $k$ — количество смежных вершин).

Пример представления неориентированного графа с использованием списка смежности (Python):

```python def adjacency_list(edges, n): 

   adj_list = [[] for _ in range(n)]
   for u, v in edges:
       adj_list[u].append(v)
       adj_list[v].append(u)  # Для неориентированного графа
   return adj_list
  1. Пример ребер графа

edges = [ 

   (0, 1),
   (0, 2),
   (1, 2),
   (1, 3),
   (2, 3)

]

n = 4 # Количество вершин adj_list = adjacency_list(edges, n) for i, neighbors in enumerate(adj_list): 

   print(f"Vertex {i}: {neighbors}")

```

Вывод:

``` Vertex 0: [1, 2] Vertex 1: [0, 2, 3] Vertex 2: [0, 1, 3] Vertex 3: [1, 2] ```

Сравнение матрицы смежности и списка смежности

Характеристика Матрица смежности Список смежности
Объем памяти $O(n^2)$ $O(n + m)$, где $n$ — количество вершин, $m$ — количество ребер
Проверка наличия ребра $O(1)$ $O(k)$, где $k$ — количество смежных вершин
Добавление вершины $O(n^2)$ (требуется изменение размера матрицы) $O(1)$
Добавление ребра $O(1)$ $O(1)$
Удаление вершины $O(n^2)$ (требуется изменение размера матрицы) $O(n + m)$ (требуется просмотр всех списков смежности)
Удаление ребра $O(1)$ $O(k)$, где $k$ — количество смежных вершин
Использование Подходит для плотных графов (большое количество ребер) Подходит для разреженных графов (малое количество ребер)

Применение

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

Понимание различных способов представления графов является важным для разработки эффективных алгоритмов работы с графами.

Источник — «http://wiki.m6a.ru/index.php?title=Представление_графов_(матрица_смежности,_список_смежности)&oldid=1119»