Воспользуемся алгоритмом поиска в глубину для реализации топологической сортировки

Теория графов

Граф состоит из вершин и ребер. Вершины графа - объекты любой природы; поскольку их должно быть конечное число, то мы будем обозначать их натуральными числами. Ребра графа соединяют некоторые из его вершин. Если ребра имеют направление, то граф называется ориентированным (орграфом); в противном случае он неориентированный. Если в графе есть ребро C из вершины A в вершину B, то говорят, что ребро C инцидентно вершинам A и B, а также что вершина A смежна с вершиной B.

	а)	б)

Рис. 1. Примеры графов

На рис. 1(а) изображен ориентированный граф. Ребра идут из вершины 1 в вершину 2, из 2 в 3, из 3 в 1, из 1 в 4, из 4 в 1, из 4 в 3. На рис. 2(б) изображен неориентированный граф. Ребра соединяют вершины 1 и 2, 1 и 4, 2 и 4, 3 и 4.

Степень вершины - число инцидентных ей ребер. Для орграфа есть входящая степень - число входящих в вершину ребер, и исходящая степень - число исходящих из вершины ребер. Вершина называется четной, если ее степень четна, и нечетной в противном случае. Вершина степени 0 называется изолированной. Путь в графе - последовательность вершин, каждые две соседние из которых смежные. Длина пути - количество вершин в нем минус 1. Если из вершины A в вершину B есть путь, то говорят, что вершина B достижима из вершины A. Путь называется простым, если все вершины в нем различны. Цикл в ориентированном графе - путь длины больше 0, в котором первая и последняя вершины совпадают. Цикл называется простым, если в нем нет совпадающих вершин, кроме первой и последней. В неориентированном графе цикл - путь длины не меньше 3, в котором первая и последняя вершины совпадают. Граф, в котором нет циклов, называется ациклическим. Неориентированный граф называется связным, если из любая его вершина достижима из любой другой. Любой неориентированный граф можно разбить накомпоненты связности, т. е. такие непересекающиеся множества вершин, что вершина A достижима из B в том и только в том случае, если эти вершины принадлежат одной компоненте связности.

В графе на рис. 1(а) вершина 1 имеет входящую степень 2, исходящую - 2, вершина 2 - 1/1, 3 - 2/1, 4 - 1/2. В графе на рис. 1(б) вершина 1 имеет степень 2, 2 - 2, 3 - 1, 4 - 3. В графе на рис. 1(а) есть пути (1, 2, 3, 1, 4) длины 4, (1, 4, 3) длины 2, (3, 1, 4, 3) длины 3, причем второй является простым, а третий - простым циклом. В графе на рис. 1(б) есть пути (1, 2, 4, 3), (1, 4), (1, 4, 2, 4), причем первые два простые, а третий - цикл. Путь (1, 2, 1) не является ни простым, ни циклом. Граф справа связный.

Полный граф - граф, в котором любая вершина смежна любой другой. Двудольный граф - граф, в котором вершины можно разбить на два множества A и B так, что никакие две вершины, принадлежащие одному множеству, не являются смежными. Ациклический неориентированный граф называют лесом, а связный лес называют деревом.

Взвешенный граф - граф, на ребрах которого написаны числа, которые называются весами ребер.

	а)	б)

Рис. 2. Пример полного и двудольного графа.

	а)	б)

Рис. 3. Пример леса и дерева

Способы представления

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

Матрица смежности графа - двумерный массив размера NxN, где N - число вершин графа. Обозначим ее за G. В обычных графах G[i, j]=1 тогда и только тогда, когда из вершины i есть ребро в вершину j; при этом в неориентированных графах G[i, j]=G[j, i]. Во взвешенных графах G[i, j] равняется весу ребра из i в j или -1, если такого ребра нет.

Матрица смежности занимает область памяти размера O(N²).

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

Списки смежности графа - линейный массив списков. Размер массива равен N; i-й элемент массива - список ребер, исходящих из вершины i. Для каждого ребра хранится вершина, в которую оно ведет и, возможно, вес ребра.

Списки смежности занимают O(M+N) памяти, где M - число ребер графа.

Поиск в глубину

Рекурсивный алгоритм:

DFS(st – вершина графа)
Вывести (st)
visited[st] ← посещена; //отметить вершину st как посещённую
Для r=1 до n выполнять
Если (graph[st][r] ≠ 0) и (visited[r] не посещена) то DFS(r)

Например, для графа, изображенного ниже, порядок обхода будет таким: 1, 4, 2, 3, 5, 6, 9, 8, 7.

Рис. 4. Граф для обхода

Поиск в ширину

BFS(st – стартовая вершина)

Вывести(st);

visited[st] ← посещена; //отметить вершину st как посещённую

Выполнить пока очередь не пуста

Для i = 0 до N

Если (graph[st][i] ≠ 0) и (visited[i] не посещена) то

Вывести(i);

visited[i] ← посещена;

Добавить вершину i в очередь;

Конец-для

Вынуть вершину из очереди в st

Конец выполнить-пока

Топологическая сортировка

Рассмотрим орграф из N вершин, не имеющий циклов. Введем на его вершинах частичное отношение порядка, а именно: вершина i считается меньше чем вершина j, если в графе есть ребро из i в j. Задача топологической сортировки состоит в том, чтобы построить для данного графа некоторый порядок обхода его вершин, причем меньшая вершина должна стоять в этом порядке позже, чем большая.

Алгоритм

Вывести (st)

Например, для графа, изображенного на рис. 5, данный алгоритм выдаст порядок обхода 5, 3, 2, 6, 1, 4.

Рис. 5. Граф для топологической сортировки

Алгоритм

Алгоритм Дейксты

Алгоритм Крускала

Перебираем рёбра

Теория графов

	а)	б)

Рис. 1. Примеры графов

Взвешенный граф - граф, на ребрах которого написаны числа, которые называются весами ребер.

	а)	б)

Рис. 2. Пример полного и двудольного графа.

	а)	б)

Рис. 3. Пример леса и дерева

Способы представления

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

Матрица смежности занимает область памяти размера O(N²).

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

Списки смежности занимают O(M+N) памяти, где M - число ребер графа.

Поиск в глубину

Рекурсивный алгоритм:

Например, для графа, изображенного ниже, порядок обхода будет таким: 1, 4, 2, 3, 5, 6, 9, 8, 7.

Рис. 4. Граф для обхода

Поиск в ширину

BFS(st – стартовая вершина)

Вывести(st);

visited[st] ← посещена; //отметить вершину st как посещённую

Выполнить пока очередь не пуста

Для i = 0 до N

Если (graph[st][i] ≠ 0) и (visited[i] не посещена) то

Вывести(i);

visited[i] ← посещена;

Добавить вершину i в очередь;

Конец-для

Вынуть вершину из очереди в st

Конец выполнить-пока

Топологическая сортировка

Алгоритм

Воспользуемся алгоритмом поиска в глубину для реализации топологической сортировки

Рекурсивный алгоритм:

DFS(st – вершина графа)
visited[st] ← посещена; //отметить вершину st как посещённую
Для r=1 до n выполнять
Если (graph[st][r] ≠ 0) и (visited[r] не посещена) то DFS(r)

Вывести (st)

Например, для графа, изображенного на рис. 5, данный алгоритм выдаст порядок обхода 5, 3, 2, 6, 1, 4.