Граф — это гибкая структура данных, которая обычно используется в качестве модели для определения отношений или связей между объектами. Объект состоит из вершин (V), а отношения или ассоциации между объектами представлены краем графа (E)Представлять.
Графы можно разделить на ориентированные графы и неориентированные графы.G=(V,E)для представления графика. Матрица смежности или список смежности часто используются для описания графа.
В базовом алгоритме графа первое, что нужно коснуться, это алгоритм обхода графа, по порядку посещения узлов его можно разделить на поиск в ширину (BFS) и поиск в глубину (DFS).
Поиск в ширину (BFS)Поиск в ширину посещает все соседние узлы текущей вершины перед дальнейшим обходом вершин в графе. А. Сначала выберите вершину в качестве начального узла и покрасьте ее в серый цвет, остальные узлы — в белый. Б. Поместите начальный узел в очередь. в) Выбрать вершину из головы очереди, найти все соседние узлы, поместить найденные соседние узлы в хвост очереди, посещенные узлы закрасить черным цветом, а непосещенные — белым. Если цвет вершины серый, значит она найдена и поставлена в очередь, если цвет вершины белый, значит она еще не найдена г. Таким же образом обработайте следующий узел в очереди. По сути, вершины, не входящие в очередь, становятся черными, те, что в очереди, — серыми, а те, что еще не присоединились к очереди, — белыми. Схема, изображающая этот процесс, выглядит следующим образом:
- Исходное состояние, начиная с вершины 1, очередь={1}
- Посетить соседние вершины 1, 1 исключено из очереди черным цветом, 2,3 поставлено в очередь, очередь={2,3,}
- Посетите соседние узлы 2, 2 исключен из очереди, 4 поставлен в очередь, очередь = {3,4}
- Посетите соседний узел 3, удалите 3 из очереди, очередь = {4}
- Посетите соседей 4, удалите 4 из очереди, queue={пусто} Узел 5 недоступен для 1. Приведенный выше граф может быть представлен следующей матрицей смежности:
int maze[5][5] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 1, 0 },
{ 0, 1, 1, 1, 0 },
{ 1, 0, 0, 0, 0 },
{ 0, 0, 1, 1, 0 }
};
Основной код BFS выглядит следующим образом:
#include <iostream>
#include <queue>
#define N 5
using namespace std;
int maze[N][N] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 1, 0 },
{ 0, 1, 1, 1, 0 },
{ 1, 0, 0, 0, 0 },
{ 0, 0, 1, 1, 0 }
};
int visited[N + 1] = { 0, };
void BFS(int start)
{
queue<int> Q;
Q.push(start);
visited[start] = 1;
while (!Q.empty())
{
int front = Q.front();
cout << front << " ";
Q.pop();
for (int i = 1; i <= N; i++)
{
if (!visited[i] && maze[front - 1][i - 1] == 1)
{
visited[i] = 1;
Q.push(i);
}
}
}
}
int main()
{
for (int i = 1; i <= N; i++)
{
if (visited[i] == 1)
continue;
BFS(i);
}
return 0;
}
Поиск в глубину (DFS)После того, как поиск в глубину посещает вершину в процессе поиска, ему необходимо рекурсивно посетить все непосещенные смежные вершины этой вершины. В начальных условиях все узлы белые, выберите один из них в качестве начальной вершины и выполните обход следующим образом: А. Выберите начальную вершину и закрасьте ее серым цветом, указывая на то, что она еще не посещалась. б. Выберите одну из смежных вершин вершины, продолжите этот процесс (то есть найдите соседние узлы соседнего узла) и углубляйтесь, пока вершина не будет иметь смежных узлов, зачерните ее, указав, что она была посещена в) Вернитесь к вершине предыдущего слоя затемненной вершины, затем найдите оставшиеся соседние узлы вершины предыдущего слоя и продолжите описанную выше операцию. Вернитесь на один уровень выше. г. Предыдущий слой продолжает выполнять описанную выше операцию до тех пор, пока не будут посещены все вершины. Более наглядно этот процесс можно изобразить на схеме:
- Исходное состояние, начиная с вершины 1
- После последовательного посещения вершин 1, 2 и 3 он заканчивается в вершине 3.
- Вернитесь из вершины 3 в вершину 2, продолжите движение к вершине 5 и закончите в вершине 5.
- Возврат из вершины 5 в вершину 2 и конец в вершине 2
- Возврат от вершины 2 к вершине 1 и завершение в вершине 1
- Доступ начинается в вершине 4 и заканчивается в вершине 4.
Приведенный выше граф может быть представлен следующей матрицей смежности:
int maze[5][5] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 0, 1 },
{ 0, 0, 1, 0, 0 },
{ 1, 1, 0, 0, 1 },
{ 0, 0, 1, 0, 0 }
};
Основной код DFS выглядит следующим образом (рекурсивная реализация):
#include <iostream>
#define N 5
using namespace std;
int maze[N][N] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 0, 1 },
{ 0, 0, 1, 0, 0 },
{ 1, 1, 0, 0, 1 },
{ 0, 0, 1, 0, 0 }
};
int visited[N + 1] = { 0, };
void DFS(int start)
{
visited[start] = 1;
for (int i = 1; i <= N; i++)
{
if (!visited[i] && maze[start - 1][i - 1] == 1)
DFS(i);
}
cout << start << " ";
}
int main()
{
for (int i = 1; i <= N; i++)
{
if (visited[i] == 1)
continue;
DFS(i);
}
return 0;
}
Нерекурсивная реализация с помощью стека выглядит следующим образом:
#include <iostream>
#include <stack>
#define N 5
using namespace std;
int maze[N][N] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 0, 1 },
{ 0, 0, 1, 0, 0 },
{ 1, 1, 0, 0, 1 },
{ 0, 0, 1, 0, 0 }
};
int visited[N + 1] = { 0, };
void DFS(int start)
{
stack<int> s;
s.push(start);
visited[start] = 1;
bool is_push = false;
while (!s.empty())
{
is_push = false;
int v = s.top();
for (int i = 1; i <= N; i++)
{
if (maze[v - 1][i - 1] == 1 && !visited[i])
{
visited[i] = 1;
s.push(i);
is_push = true;
break;
}
}
if (!is_push)
{
cout << v << " ";
s.pop();
}
}
}
int main()
{
for (int i = 1; i <= N; i++)
{
if (visited[i] == 1)
continue;
DFS(i);
}
return 0;
}
В некоторых DFS можно сначала получить доступ к узлу чтения, а затем больше не выводить узел при откате. Отличие алгоритма от моего в том, что тайминги точки вывода разные, а идея та же. DFS имеет хорошие приложения как для кольцевого мониторинга, так и для топологической сортировки.
PS: Картинки и тексты все мои авторские. Рисовала несколько часов. Перепечатайте и укажите источник. Уважение к интеллектуальному труду, спасибо~