Структуры данных - Граф
Граф — это более общая нелинейная структура данных, используемая для представления сложных отношений «многие ко многим» между элементами, состоящая из вершин и ребер, соединяющих вершины.
Основные понятия графов
Типы графовТипы графов — неориентированный граф, ориентированный граф, взвешенный граф
Неориентированный граф
0
—1
Рёбра не имеют направления; связи взаимны.
Пример: дружеские связи в социальной сети
Пример: дружеские связи в социальной сети
Ориентированный граф
0
→1
Рёбра имеют направление; связи односторонние.
Пример: подписки, ссылки между веб-страницами
Пример: подписки, ссылки между веб-страницами
Взвешенный граф
0
51
Рёбра имеют веса (расстояние/стоимость)
Пример: навигация по карте, сетевая задержка
Пример: навигация по карте, сетевая задержка
Способы хранения графа
Сравнение способов храненияМатрица смежности против списка смежности
Матрица смежности
Пространственная сложность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;
}
#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, обнаружение сообществ |
| Другие расширения | ИИ думает... |