07.02.240 Структуры данных для графов - justjune/AiSD2026 GitHub Wiki
Структуры данных для графов
Структура данных для графа — это способ хранения и организации вершин (узлов) и рёбер (связей между ними) в памяти компьютера, который позволяет эффективно выполнять обходы, поиски и другие алгоритмы. Двумя основными структурами данных для графов являются матрицы смежности (adjacency matrix) и списки смежности (adjacency list).
Матрица смежности
Матрица смежности — это квадратная матрица M размером n × n (где n — количество вершин графа), используемая для представления графа G = (V, E). Она формируется так:
- M[i, j] = 1, если существует ребро между вершинами i и j
- M[i, j] = 0, если ребро между вершинами i и j отсутствует
Плюсы: Скорость. Можем очень быстро проверить, соединены ли две точки, или мгновенно добавить/удалить связь.
Минусы: Она занимает неоправданно много памяти, если связей в графе мало.
Пример: Карта Манхэттена. 3000 перекрестков (вершин) и 6000 дорог (ребер). Связей не так много, но нам придется создать таблицу размером 3000 × 3000 = 9 миллионов ячеек. И почти все 9 миллионов ячеек будут заполнены бесполезными нулями.
Списки смежности
Списки смежности — это структура данных, в которой для каждой вершины графа хранится список всех смежных с ней вершин (соседних вершин, соединённых рёбрами).
Плюсы:
- Экономия памяти (особенно для графов, где мало связей), так как мы храним только существующие рёбра.
- Быстрый обход графа.
- Легко добавлять или удалять вершины и рёбра.
Минусы:
- Медленная проверка наличия ребра. Чтобы узнать, есть ли ребро (i,j), нужно перебрать весь список соседей вершины i.
Списки смежности можно использовать для большинства задач, особенно если граф разреженный. Матрицу смежности — если граф плотный или нужно очень часто проверять наличие конкретных рёбер.
Реализация графов посредством списков смежности
#define MAXV 100 /* Максимальное количество вершин */
typedef struct edgenode {
int y; /* Номер соседней вершины */
int weight; /* Вес ребра, если есть */
struct edgenode *next; /* Следующее ребро в списке */
} edgenode;
typedef struct {
edgenode *edges[MAXV+1]; /* Массив указателей(для каждой вершины свой список рёбер) */
int degree[MAXV+1]; /* Количество соседей каждой вершины */
int nvertices; /* Количество вершин в графе */
int nedges; /* Количество ребер в графе */
int directed; /* Граф ориентированный? */
} graph;
Сравнение матриц и списков смежности
Словарь терминов:
Графом называется упорядоченная пара множеств G = (V, Е), где V- подмножество вершин (или узлов), а Е- упорядоченное или неупорядоченное подмножество ребер, соединяющих пары вершин из V.
Граф является разреженным (sparse), когда в действительности ребра определены только для малой части возможных пар вершин.
Граф, у которого ребра определены для большей части возможных пар вершин, называется плотным (dense).
Вес ребра — значение, поставленное в соответствие данному ребру взвешенного графа. Обычно вес — вещественное число, в таком случае его можно интерпретировать как длину ребра.
Взвешенный граф — граф, каждому ребру которого поставлено в соответствие некое значение вес ребра.
Литература
https://djvu.online/file/3wrno0HyEnchM?ysclid=mty1fzeln9926949060
https://www.youtube.com/live/HoMZt-eWzLo?si=JLf7QRILOrcWFLFG