Назад

Методы программирования

Задание 4. Топологическая сортировка вершин графа

Общая информация

Задание состоит из двух частей, первая из которых обязательны для выполнения, вторая выполняется для получения оценки «отлично».

Теория

Бинарным отношением на множестве A будем называть подмножество декартова произведения M x M, т.е. некоторое множество упорядоченных пар, каждый элемент которых является элементом множества A. Например, отношение > (больше) является бинарным отношением на множестве {1, 2, 3, 4} и содержит пары (2, 1), (3, 1), (4, 1), (3, 2), (4, 2), (4, 3). Будем говорить, что истинно утверждение a R b, если пара (a, b) принадлежит бинарному отношению R.

Пусть дано некоторое бинарное отношение R на конечном множестве A. Задачей топологической сортировки является выстраивание элементов множества A в последовательность a1, a2, ..., aN так, что для любой пары (ai, aj) такой, что истинно ai R aj, выполняется условие i < j.

Если представить отношение в виде ориентированного графа (элементы множества являются вершинами, ребро из вершины a в вершину b существует тогда и только тогда, когда истинно a R b), то задача может быть сформулирована следующим образом: перечислить вершины графа в таком порядке, чтобы для любого ребра графа его начальная вершина была перечислена раньше конечной. На рисунке слева изображен исходный граф, справа его вершины перечислены в требуемом порядке.

Пример топологической сортировки графа

Можно привести следующий пример использования топологической сортировки: допустим, есть некоторое количество заданий, причем выполнение некоторых из них невозможно до тех пор, пока не будут выполнены какие-либо другие задания. Это множество заданий представляется в виде ориентированного графа, а в результате топологической сортировки вершин этого графа определяется последовательность выполнения заданий, удовлетворяющая всем условиям.

Ясно, что выполнить топологическую сортировку возможно не в любом графе, а только в таком, в котором отсутствуют циклы. Описанный ниже алгоритм выполняет топологическую сортировку графа без циклов.

  1. Помечаем все вершины графа как неиспользованные.
  2. Ищем неиспользованную вершину, в которую не входит ни одно ребро (в соответствующем столбце матрицы смежности стоят только нули). Если такой вершины нет, то либо мы перебрали все вершины (топологическая сортировка закончена), либо в графе есть цикл (топологическая сортировка невозможна).
  3. Помечаем найденную вершину как использованную, печатаем ее номер.
  4. Удаляем из графа все ребра с началом в этой вершине (зануляется соответствующая строка матрицы смежности).
  5. Переходим к шагу 2.

Для ускорения работы алгоритма можно хранить в массиве количество ребер, входящих в данную вершину, и обновлять это количество при удалении каждого ребра.

Формулировка задания

a. Реализация на матрицах смежности.

Во входном файле input.txt вводится граф в виде списка ребер. Считать его в матрицу смежности (двумерный массив, элемент (i, j) которого равен 1, если в графе есть ребро из вершины i в вершину j, и 0 в противном случае) и выполнить топологическую сортировку этого графа. Результат (последовательность вершин или сообщение о наличии цикла в графе) выдать в файл output.txt.

b. *Реализация на списках смежности.

То же задание, но граф хранить в виде списка смежности (для каждой вершины хранится список вершин, в которые есть ребро из данной вершины).