Структуры данных - Граф

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


Основные понятия графов

Типы графов

Типы графов — неориентированный граф, ориентированный граф, взвешенный граф

Неориентированный граф

0
—
1
Рёбра не имеют направления; связи взаимны.
Пример: дружеские связи в социальной сети

Ориентированный граф

0
→
1
Рёбра имеют направление; связи односторонние.
Пример: подписки, ссылки между веб-страницами

Взвешенный граф

0
5
1
Рёбра имеют веса (расстояние/стоимость)
Пример: навигация по карте, сетевая задержка

Способы хранения графа

Сравнение способов хранения

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

Матрица смежности

Пространственная сложностьO(V²)
Проверить, соединены ли две вершиныO(1)
Обход смежных вершинO(V)
Подходит для: плотных графов · int graph[V][V]

Список смежности

Пространственная сложностьO(V+E)
Проверить, соединены ли две вершиныO(degree)
Обход смежных вершинO(degree)
Подходит для: разреженных графов · Массив связных списков

Обход графа

DFS против BFS — обход, начиная с вершины 0

DFS: поиск в глубину

0→ 1→ 3→ 4→ 2→ 5
Идём по одному пути до конца, затем возвращаемся назад
Реализация: рекурсия / стек | Подходит для поиска путей, топологической сортировки

BFS: поиск в ширину

0→ 1→ 2→ 3→ 4→ 5
Расширение слой за слоем; сначала посещаются узлы одного уровня
Реализация: очередь | Естественно подходит для поиска кратчайших путей в невзвешенных графах

Примеры

#include <stdio.h>
#include <stdbool.h>

#define V 6 /* число вершин */

/* Граф представлен матрицей смежности */
int graph[V][V] = {
    {0,1,1,0,0,0},  /* Связи смежности вершины 0 */
    {1,0,0,1,1,0},  /* Вершина 1 */
    {1,0,0,0,1,0},  /* Вершина 2 */
    {0,1,0,0,0,1},  /* Вершина 3 */
    {0,1,1,0,0,1},  /* Вершина 4 */
    {0,0,0,1,1,0}   /* Вершина 5 */
};
bool visited[V];

/* DFS: поиск в глубину, рекурсивная реализация Особенности: идёт по одному пути до конца и возвращается назад, подходит для поиска пути и проверки связности */
/* Посетить текущую вершину */

void DFS(int v) {
    visited[v] = true;
    printf("%d ", v);         /* Рекурсивно посетить непосещённые смежные вершины */
    for (int i = 0; i < V; i++) {
        if (graph[v][i] && !visited[i]) {
            DFS(i);  /* BFS: поиск в ширину, реализован с использованием очереди Особенности: расширяется слой за слоем, естественно подходит для поиска кратчайших путей */
        }
    }
}

/* Добавить начальную вершину в очередь */
/* Извлечь из очереди */

void BFS(int start) {
    bool visited[V] = {false};
    int queue[V];
    int front = 0, rear = 0;

    visited[start] = true;
    queue[rear++] = start;  /* Добавить смежные вершины в очередь */

    while (front < rear) {
        int v = queue[front++];  /* Инициализировать флаги посещения */
        printf("%d ", v);

        for (int i = 0; i < V; i++) {
            if (graph[v][i] && !visited[i]) {
                visited[i] = true;
                queue[rear++] = i;  "DFS (начиная с вершины 0): "
            }
        }
    }
}

int main() {
    /* Вывод: 0 1 3 5 4 2 */
    for (int i = 0; i < V; i++) visited[i] = false;

    printf("BFS (начиная с вершины 0): ");
    DFS(0);  /* Вывод: 0 1 2 3 4 5 */
    printf("\n");

    printf(Сценарии применения графов);
    BFS(0);  Сценарии
    printf("\n");
    return 0;
}

Сценарии применения графов

Кратчайший путьDijkstra, Bellman-Ford (навигация по картам)
Минимальное остовное деревоPrim, Kruskal (оптимизация прокладки сетевых кабелей)
Топологическая сортировкаАлгоритм Кана (анализ зависимостей задач)
Анализ социальных сетейPageRank, обнаружение сообществ
Другие расширенияИИ думает...
Структуры данных – Куча