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

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

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

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

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

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

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

=== Пример представления неориентированного графа с использованием матрицы смежности (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

# Пример графа в виде списка смежности
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) ==

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

# '''Представление неориентированного графа''': В неориентированном графе список смежности для каждой вершины содержит все вершины, с которыми она связана.
# '''Представление ориентированного графа''': В ориентированном графе список смежности для каждой вершины содержит только те вершины, в которые есть ребро из данной вершины.
# '''Представление взвешенного графа''': Во взвешенном графе в списке смежности для каждой вершины хранятся пары (соседняя вершина, вес ребра).
# '''Преимущества''':
## Экономия памяти при работе с разреженными графами.
## Удобство добавления и удаления вершин и ребер.
# '''Недостатки''':
## Более сложная реализация по сравнению с матрицей смежности.
## Более медленная проверка наличия ребра между двумя вершинами (за время $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

# Пример ребер графа
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]
```

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

{| class="wikitable"
|-
! Характеристика
! Матрица смежности
! Список смежности
|-
! Объем памяти
| $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$ — количество смежных вершин
|-
! Использование
| Подходит для плотных графов (большое количество ребер)
| Подходит для разреженных графов (малое количество ребер)
|}

== Применение ==

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

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