Граф – совокупность точек, соединенных линиями. Точки называются вершинами, или узлами, а линии – ребрами, или дугами.
Степень входа вершины – количество входящих в нее ребер, степень выхода – количество исходящих ребер.
Граф, содержащий ребра между всеми парами вершин, является полным.
Встречаются такие графы, ребрам которых поставлено в соответствие конкретное числовое значение, они называются взвешенными графами, а это значение – весом ребра.
Когда у ребра оба конца совпадают, т.е. оно выходит из вершины и входит в нее, то такое ребро называется петлей.
Классификация графов
Графы делятся на
- связные
- несвязные
В связном графе между любой парой вершин существует как минимум один путь.
В несвязном графе существует хотя бы одна вершина, не связанная с другими.
Графы также подразделяются на
- ориентированные
- неориентированные
- смешанные.
В ориентированном графе ребра являются направленными, т.е. существует только одно доступное направление между двумя связными вершинами.
В неориентированном графе по каждому из ребер можно осуществлять переход в обоих направлениях.
Частный случай двух этих видов – смешанный граф. Он характерен наличием как ориентированных, так и неориентированных ребер.
Способы представления графа
Граф может быть представлен (сохранен) несколькими способами:
- матрица смежности;
- матрица инцидентности;
- список смежности (инцидентности);
- список ребер.
Использование двух первых методов предполагает хранение графа в виде двумерного массива (матрицы). Размер массива зависит от количества вершин и/или ребер в конкретном графе.
Матрица смежности графа — это квадратная матрица, в которой каждый элемент принимает одно из двух значений: 0 или 1.
Число строк матрицы смежности равно числу столбцов и соответствует количеству вершин графа.
- 0 – соответствует отсутствию ребра,
- 1 – соответствует наличию ребра.
Когда из одной вершины в другую проход свободен (имеется ребро), в ячейку заносится 1, иначе – 0. Все элементы на главной диагонали равны 0 если граф не имеет петель.
Матрица инцидентности (инциденции) графа — это матрица, количество строк в которой соответствует числу вершин, а количество столбцов – числу рёбер. В ней указываются связи между инцидентными элементами графа (ребро(дуга) и вершина).
В неориентированном графе если вершина инцидентна ребру то соответствующий элемент равен 1, в противном случае элемент равен 0.
В ориентированном графе если ребро выходит из вершины, то соответствующий элемент равен 1, если ребро входит в вершину, то соответствующий элемент равен -1, если ребро отсутствует, то элемент равен 0.
Матрица инцидентности для своего представления требует нумерации рёбер, что не всегда удобно.
Список смежности (инцидентности)
Если количество ребер графа по сравнению с количеством вершин невелико, то значения большинства элементов матрицы смежности будут равны 0. При этом использование данного метода нецелесообразно. Для подобных графов имеются более оптимальные способы их представления.
По отношению к памяти списки смежности менее требовательны, чем матрицы смежности. Такой список можно представить в виде таблицы, столбцов в которой – 2, а строк - не больше, чем вершин в графе.
В каждой строке в первом столбце указана вершина выхода, а во втором столбце – список вершин, в которые входят ребра из текущей вершины.
Преимущества списка смежности:
- Рациональное использование памяти.
- Позволяет быстро перебирать соседей вершины.
- Позволяет проверять наличие ребра и удалять его.
Недостатки списка смежности:
- При работе с насыщенными графами (с большим количеством рёбер) скорости может не хватать.
- Нет быстрого способа проверить, существует ли ребро между двумя вершинами.
- Количество вершин графа должно быть известно заранее.
- Для взвешенных графов приходится хранить список, элементы которого должны содержать два значащих поля, что усложняет код:
- номер вершины, с которой соединяется текущая;
- вес ребра.
Список рёбер
В списке рёбер в каждой строке записываются две смежные вершины и вес соединяющего их ребра (для взвешенного графа).
Количество строк в списке ребер всегда должно быть равно величине, получающейся в результате сложения ориентированных рёбер с удвоенным количеством неориентированных рёбер.
Какой способ представления графа лучше? Ответ зависит от отношения между числом вершин и числом рёбер. Число ребер может быть довольно малым (такого же порядка, как и количество вершин) или довольно большим (если граф является полным). Графы с большим числом рёбер называют плотными, с малым - разреженными. Плотные графы удобнее хранить в виде матрицы смежности, разреженные - в виде списка смежности.
Алгоритмы обхода графов
Основными алгоритмами обхода графов являются
Поиск в ширину подразумевает поуровневое исследование графа:
- вначале посещается корень – произвольно выбранный узел,
- затем – все потомки данного узла,
- после этого посещаются потомки потомков и т.д.
Вершины просматриваются в порядке возрастания их расстояния от корня.
Алгоритм прекращает свою работу после обхода всех вершин графа, либо в случае выполнения требуемого условия (например, найти кратчайший путь из вершины 1 в вершину 6).
Каждая вершина может находиться в одном из 3 состояний:
- 0 - оранжевый – необнаруженная вершина;
- 1 - зеленый – обнаруженная, но не посещенная вершина;
- 2 - серый – обработанная вершина.
Фиолетовый – рассматриваемая вершина.
Применения алгоритма поиска в ширину
- Поиск кратчайшего пути в невзвешенном графе (ориентированном или неориентированном).
- Поиск компонент связности.
- Нахождения решения какой-либо задачи (игры) с наименьшим числом ходов.
- Найти все рёбра, лежащие на каком-либо кратчайшем пути между заданной парой вершин.
- Найти все вершины, лежащие на каком-либо кратчайшем пути между заданной парой вершин.
Алгоритм поиска в ширину работает как на ориентированных, так и на неориентированных графах.
Для реализации алгоритма удобно использовать очередь.
Реализация на C++ (с использованием очереди STL)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <queue> // очередь
using namespace std;
int main()
{
queue<int> Queue;
int mas[7][7] = { { 0, 1, 1, 0, 0, 0, 1 }, // матрица смежности
{ 1, 0, 1, 1, 0, 0, 0 },
{ 1, 1, 0, 0, 0, 0, 0 },
{ 0, 1, 0, 0, 1, 0, 0 },
{ 0, 0, 0, 1, 0, 1, 0 },
{ 0, 0, 0, 0, 1, 0, 1 },
{ 1, 0, 0, 0, 0, 1, 0 } };
int nodes[7]; // вершины графа
for (int i = 0; i < 7; i++)
nodes[i] = 0; // исходно все вершины равны 0
Queue.push(0); // помещаем в очередь первую вершину
while (!Queue.empty())
{ // пока очередь не пуста
int node = Queue.front(); // извлекаем вершину
Queue.pop();
nodes[node] = 2; // отмечаем ее как посещенную
for (int j = 0; j < 7; j++)
{ // проверяем для нее все смежные вершины
if (mas[node][j] == 1 && nodes[j] == 0)
{ // если вершина смежная и не обнаружена
Queue.push(j); // добавляем ее в очередь
nodes[j] = 1; // отмечаем вершину как обнаруженную
}
}
cout << node + 1 << endl; // выводим номер вершины
}
cin.get();
return 0;
}
Результат выполнения
Задача поиска кратчайшего пути
Реализация на С++
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <queue> // очередь
#include <stack> // стек
using namespace std;
struct Edge {
int begin;
int end;
};
int main()
{
system("chcp 1251");
system("cls");
queue<int> Queue;
stack<Edge> Edges;
int req;
Edge e;
int mas[7][7] = { { 0, 1, 1, 0, 0, 0, 1 },
{ 1, 0, 1, 1, 0, 0, 0 },
{ 1, 1, 0, 0, 0, 0, 0 },
{ 0, 1, 0, 0, 1, 0, 0 },
{ 0, 0, 0, 1, 0, 1, 0 },
{ 0, 0, 0, 0, 1, 0, 1 },
{ 1, 0, 0, 0, 0, 1, 0 } };
int nodes[7]; // вершины графа
for (int i = 0; i < 7; i++) // исходно все вершины равны 0
nodes[i] = 0;
cout << "N = "; cin >> req; req--;
Queue.push(0); // помещаем в очередь первую вершину
while (!Queue.empty())
{
int node = Queue.front(); // извлекаем вершину
Queue.pop();
nodes[node] = 2; // отмечаем ее как посещенную
for (int j = 0; j < 7; j++)
{
if (mas[node][j] == 1 && nodes[j] == 0)
{ // если вершина смежная и не обнаружена
Queue.push(j); // добавляем ее в очередь
nodes[j] = 1; // отмечаем вершину как обнаруженную
e.begin = node; e.end = j;
Edges.push(e);
if (node == req) break;
}
}
cout << node + 1 << endl; // выводим номер вершины
}
cout << "Путь до вершины " << req + 1 << endl;
cout << req + 1;
while (!Edges.empty()) {
e = Edges.top();
Edges.pop();
if (e.end == req) {
req = e.begin;
cout << " <- " << req + 1;
}
}
cin.get(); cin.get();
return 0;
}
Результат выполнения
Поиск в глубину – это алгоритм обхода вершин графа.
Поиск в ширину производится симметрично (вершины графа просматривались по уровням). Поиск в глубину предполагает продвижение вглубь до тех пор, пока это возможно. Невозможность продвижения означает, что следующим шагом будет переход на последний, имеющий несколько вариантов движения (один из которых исследован полностью), ранее посещенный узел (вершина).
Отсутствие последнего свидетельствует об одной из двух возможных ситуаций:
- все вершины графа уже просмотрены,
- просмотрены вершины доступные из вершины, взятой в качестве начальной, но не все (несвязные и ориентированные графы допускают последний вариант).
Каждая вершина может находиться в одном из 3 состояний:
- 0 - оранжевый – необнаруженная вершина;
- 1 - зеленый – обнаруженная, но не посещенная вершина;
- 2 - серый – обработанная вершина;
Фиолетовый – рассматриваемая вершина.
Применения алгоритма поиска в глубину
- Поиск любого пути в графе.
- Поиск лексикографически первого пути в графе.
- Проверка, является ли одна вершина дерева предком другой.
- Поиск наименьшего общего предка.
- Топологическая сортировка.
- Поиск компонент связности.
Алгоритм поиска в глубину работает как на ориентированных, так и на неориентированных графах. Применимость алгоритма зависит от конкретной задачи.
Для реализации алгоритма удобно использовать стек или рекурсию.
Реализация на C++ (с использованием стека STL)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stack> // стек
using namespace std;
int main()
{
stack<int> Stack;
int mas[7][7] = { { 0, 1, 1, 0, 0, 0, 1 }, // матрица смежности
{ 1, 0, 1, 1, 0, 0, 0 },
{ 1, 1, 0, 0, 0, 0, 0 },
{ 0, 1, 0, 0, 1, 0, 0 },
{ 0, 0, 0, 1, 0, 1, 0 },
{ 0, 0, 0, 0, 1, 0, 1 },
{ 1, 0, 0, 0, 0, 1, 0 } };
int nodes[7]; // вершины графа
for (int i = 0; i < 7; i++) // исходно все вершины равны 0
nodes[i] = 0;
Stack.push(0); // помещаем в очередь первую вершину
while (!Stack.empty())
{ // пока стек не пуст
int node = Stack.top(); // извлекаем вершину
Stack.pop();
if (nodes[node] == 2) continue;
nodes[node] = 2; // отмечаем ее как посещенную
for (int j = 6; j >= 0; j--)
{ // проверяем для нее все смежные вершины
if (mas[node][j] == 1 && nodes[j] != 2)
{ // если вершина смежная и не обнаружена
Stack.push(j); // добавляем ее в cтек
nodes[j] = 1; // отмечаем вершину как обнаруженную
}
}
cout << node + 1 << endl; // выводим номер вершины
}
cin.get();
return 0;
}
Результат выполнения
Задача поиска лексикографически первого пути на графе.
Реализация на C++
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
//#include <queue> // очередь
#include <stack> // стек
using namespace std;
struct Edge {
int begin;
int end;
};
int main()
{
system("chcp 1251");
system("cls");
stack<int> Stack;
stack<Edge> Edges;
int req;
Edge e;
int mas[7][7] = { { 0, 1, 1, 0, 0, 0, 1 }, // матрица смежности
{ 1, 0, 1, 1, 0, 0, 0 },
{ 1, 1, 0, 0, 0, 0, 0 },
{ 0, 1, 0, 0, 1, 0, 0 },
{ 0, 0, 0, 1, 0, 1, 0 },
{ 0, 0, 0, 0, 1, 0, 1 },
{ 1, 0, 0, 0, 0, 1, 0 } };
int nodes[7]; // вершины графа
for (int i = 0; i < 7; i++) // исходно все вершины равны 0
nodes[i] = 0;
cout << "N = ";
cin >> req;
req--;
Stack.push(0); // помещаем в очередь первую вершину
while (!Stack.empty())
{ // пока стек не пуст
int node = Stack.top(); // извлекаем вершину
Stack.pop();
if (nodes[node] == 2) continue;
nodes[node] = 2; // отмечаем ее как посещенную
for (int j = 6; j >= 0; j--)
{ // проверяем для нее все смежные вершины
if (mas[node][j] == 1 && nodes[j] != 2)
{ // если вершина смежная и не обнаружена
Stack.push(j); // добавляем ее в cтек
nodes[j] = 1; // отмечаем вершину как обнаруженную
e.begin = node; e.end = j;
Edges.push(e);
if (node == req) break;
}
}
cout << node + 1 << endl; // выводим номер вершины
}
cout << "Путь до вершины " << req + 1 << endl;
cout << req + 1;
while (!Edges.empty())
{
e = Edges.top();
Edges.pop();
if (e.end == req)
{
req = e.begin;
cout << " <- " << req + 1;
}
}
cin.get(); cin.get();
return 0;
}
Результат выполнения
Поиск в глубину также может быть реализован с использованием рекурсивного алгоритма.
Реализация обхода графа в глубину на C++ (с использованием рекурсии)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
using namespace std;
int mas[7][7] = { { 0, 1, 1, 0, 0, 0, 1 }, // матрица смежности
{ 1, 0, 1, 1, 0, 0, 0 },
{ 1, 1, 0, 0, 0, 0, 0 },
{ 0, 1, 0, 0, 1, 0, 0 },
{ 0, 0, 0, 1, 0, 1, 0 },
{ 0, 0, 0, 0, 1, 0, 1 },
{ 1, 0, 0, 0, 0, 1, 0 } };
int nodes[7]; // вершины графа
void search(int st, int n)
{
int r;
cout << st + 1 << " ";
nodes[st] = 1;
for (r = 0; r < n; r++)
if ((mas[st][r] != 0) && (nodes[r] == 0))
search(r, n);
}
int main()
{
for (int i = 0; i < 7; i++) // исходно все вершины равны 0
nodes[i] = 0;
search(0, 7);
cin.get();
return 0;
}
Результат выполнения
Пример использования графов - алгоритм Дейкстры нахождения кратчайшего пути во взвешенных графах.
А как сделать обход в ширину используя матрицу инцидентности графа? Идти по столбам?
Здравствуйте, а как определить смежны ли две вершины в неориентированном графе, используя список смежности, а не матрицу. Заранее спасибо.
Просмотреть список для одной из вершин и найти в нем другую вершину
Прошу прощения заранее. Нет ли примера поиска пути смешанного графа, представленного в виде списка ребёр?
Пример есть только через матрицу. Остальное надо делать 🙂
Честно говоря есть проблемы с понимаем теории нахождения пути в графе, где заданы только его рёбра. Как дальше обычно решают подобные задачи, делают преобразование списка ребёр в матрицу смежности или какой-то уникальный способ решения для этого есть?
p.s. А если там будет скажем больше 100 вершин будет в графе, тогда ведь матрицу вычислительной машине сложно будет уже реализовать 🙂
Не обязательно строить матрицу. Можно обойти ребра, обойдя начальную и конечную вершину каждого. А если ребра отсортированы по начальной вершине, то алгоритм обхода ещё упростится, потому что обойти нужно несколько последовательных ребер для каждой рассматриваемой вершины
https://e-maxx.ru/algo/ford_bellman
Добрый день, а вы не моглибы выложить код для : Список смежности (инцидентности) используя поиск в ширину. Заранее спасибо.
Возможно, выложу, когда будет время.
Если кто-нибудь готов поделиться кодом, буду благодарна.
Интересует такой вопрос, если граф будет несвязным, то есть состоять из 2 или более компонент, как можно было бы в коде описать этот момент, чтобы вывелись все компоненты и связные и отдельные(несвязные)
Например, если граф задаётся матрицей смежности, то обход осуществляется по строкам и столбцам. И если перебрать все строки в цикле, то мы обратимся к каждой вершине, связной или не связной
Ну вот на примере вашей реализации поиска с использованием стека, выводятся все связные вершины, а дополнительно к этому как ещё вывести не связные, это нужно в этот же цикл for дописать определенное условие какое то?
Задача с использованием стека — это поиск пути. Если граф не связный, то пути между несвязанными вершинами нет, и можно его не искать.
Почему "Применения алгоритма поиска в ширину" выдает неправильный ответ при использовании 8 вершин? Ответ должен быть 1 2 4 6 7 1 3 5 8, и ответ должен быть выведен 1 2 4 6 7 9 3 5 8. Матрица, которую я использовал:
2
3
4
5
6
7
8
{ 1, 0, 0, 1, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 1, 0, 0, 0 },
{ 1, 1, 0, 0, 0, 1, 1, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 1 },
{ 0, 0, 0, 1, 0, 0, 1, 0 },
{ 0, 0, 0, 1, 0, 1, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 0, 0 }};
Откуда 9, если 8 вершин?
Я не знаю. вот ответ, который я получаю
Значит, там должна быть 1
А как сделать обход графа в ширину, используя список смежности?
Для каждой вершины есть список вершин, в которые есть путь. Нужно перебрать все элементы списка и добавить в очередь непосещенные вершины. Потом извлекать из очереди по одной и просматривать следующие уровни.
Здравствуйте! Как преобразовать матрицу инциденций в списки инцидентности? С++
Создать количество списков, равное количеству вершин. Выполнить цикл для всех ребер матрицы инцидентности. Добавить каждое ребро для той вершины, для которой в соответствующей строке содержится -1. Если -1 нет, то добавить два ребра для вершин, содержащих 1 в соответствующих строках
Интересная тема. Кстати, ставить return 0; нужно. Это, как минимум, не повредит.
Как раз повредит! Функция типа void не имеет возврата, а значит возвращать целое число (0) нельзя!
отличный мануал!
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <vector>
#include <queue>
using namespace std;
int main()
{
long n;
cin >> n;
vector < vector <long> > a(n, vector <long> (n));
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
cin >> a[i][j];
}
}
for(int k = 0; k < n; k++)
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(a[i][j] > a[i][k] + a[k][j])
{
a[i][j] = a[i][k] + a[k][j];
}
}
}
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
cout << a[i][j] << ' ';
}
cout << "\n";
}
return 0;
}
Здравствуйте. А как найти максимальный путь? В каком месте кода этот алгоритм реализуется?
Приводится лексикографический обход. А что это за обход и зачем он нужен?
Это обход через вершины с наименьшими номерами
А как найти кратчайший путь, если таких несколько найти лексикографически меньший по пронумерованным рёбрам?
Выведется лексикографически первый
Нет, Вы неправильно поняли. Нужно найти кратчайший путь в графе, если таких путей несколько, выбирается лексикографически наименьший по заранее пронумерованным рёбрам (номера могут повторяться).
Елена, а Вы не пробовали заниматься разработкой в Linux? Во многих вещах к программисту Linux гораздо более дружелюбен (если только не писать конкретно под Windows). Там замечательный терминал (никакие «гетчары» не потребуются), всё прозрачно и удобно, по умолчанию — «человеческая» кодировка utf-8. И программного обеспечения, причем отличного, вагон и маленькая тележка: Geany, Atom, QtCreator, KDevelop, Visual Studio Code. Всё бесплатное, с обновлением через репозитории.
Пока меня жизнь с Linuxом не сталкивала
Возможно, стоит попробовать — вдруг понравится 🙂 В Linux очень удобный терминал, причем работа с терминалом — «родной» режим для Linux, мощная командная оболочка Bash. Значительная часть ПО с открытым исходным кодом — всегда можно посмотреть, как что устроено и как оно работает. Особенно Linux удобен для разработки серверных приложений, так как на большинстве серверов установлен какой-нибудь из дистрибутивов Linux (или Unix-подобный). Поэтому разработка/настройка/перенос происходят «органично» (кстати, если Web-сайт с php, то этот Web-сайт в известном смысле тоже серверное приложение — php выполняется на сервере). А еще — есть «дружелюбные» дистрибутивы Linux, которые в использовании не сложнее любого Windows (Linux Mint например).
Это костыли и велосипеды с кодировками. Просто используйте юникод.Консоль прекрасно поддерживает юникод, для этого есть функция WriteConsoleW. Она с буквой W на конце, а значит, принимает юникодные символы для вывода на консоль.
По поводу функции main() когда пишешь основную программу, то ты ей задаёшь тип void main(), int main() и т.п. так вот, если ты пишешь void main(), там не надо ставить return т.к. void ничего не возрващает, а float, int char и т.п. возвращают по этому в конце программы необходимо ставить return 1 или другое любое число. По поводу кирилицы, необходимо подключить библиотеку срусским языком, или это проблема именно в самом коде, т.к. в коде кирилица(названии операторов и т.п.)
По поводу функции main() — в программах для персонального компьютера хорошим тоном является использование int main() и возврат операционной системе значения 0.
Если, например, это — программа для микроконтроллера, то она будет представлять собой бесконечный цикл и завершаться по сбросу питания. В этом случае мы используем void main(), потому что return после бесконечного цикла попросту недостижим.
Что касается кириллицы, то проблема возникает из-за разной кодировки в Windows-окне и в окне консоли. Так, стандартные Windows-приложения (в том числе Visual Studio) используют кодовую страницу ASCII-1251, в то время как окно консоли после запуска работает с кодовой страницей ASCII-866. Поэтому в программах приходится использовать дополнительные средства, чтобы привести эти кодовые страницы в соответствие.
Интересный вопрос — в Windows 10 не линкуется код с DX 9. А в ХР все нормально.
Сам недавно узнал — в функции main() не нужно ставить «return 0» он там есть уже по умолчанию.
Код с кириллицей не компилируется в MinGW, а в Visual Studio все нормально.
Вообще-то рекомендуется ставить return 0; он говорит, что программа успешно кончилась, а кириллицу можно подключить в С++, так что не стоит говорить вещей, которых вы не знаете.