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

Если в ориентированном графе нет контуров (путей у которых начальная и конечная вершины совпадают), то можно перенумеровать вершины данного графа таким образом, что для каждой дуги (i,j) будет выполняться условие i<j. Такая перенумерация верши называется топологической сортировкой графа.

На рис.7.19 приведен топологически отсортированный и не отсортированный граф.

 

 

Алгоритм топологической сортировки может быть следующим:

1. Присвоить номер 1 вершине графа, в которую нет входящих дуг.

2. Присвоить следующий номер любой неперенумерованной вершине, для которой все предшествующие вершины перенумерованы. Здесь под предшествующими вершинами некоторой вершины u понимаются все вершины v, такие, что дуга (v,u) принадлежит множеству дуг графа. Если на данном шаге нет неперенумерованных вершины, для которой все предшествующие вершины перенумерованы, то это говорит о том, что исходный граф содержит контур (граф не может быть топологически отсортирован) и требуется остановить процесс перенумерации вершин.

3. Шаг 2 повторяется до тех пор, пока все вершины не будут перенумерованы.

Алгоритм топологической сортировки графа представлен укрупненной блок-схемой на рис.7.20. Программная реализация этого алгоритма представлена в листинге 7.11. В данном листинге граф задан матрицей смежности, элементы которой имеют логический тип. Далее (см. разд.7.5.1) возникнет необходимость осуществлять топологическую сортировку графа заданного матрицей весов, элементы которой имеют целочисленный тип. В связи с этим в листинге 7.11 проверка принадлежности дуги (i,j) графу оформлена в виде отдельной функции EDuga. Это позволит свести к минимуму изменения при переходе к хранению графа с помощью матрицы весов. Данные изменения затронут только функцию EDuga.

Топологическую сортировку графа можно выполнить и другим способом:

1. Присвоить переменной k значение n, где n - число вершин графа.

2. Найти вершину u, из которой нет выходящих дуг и присвоить ей номер k. Если на данном шаге нет вершины, из которой нет выходящих дуг, то это говорит о том, что исходный граф содержит контур и требуется остановить процесс перенумерации вершин.

3. Удалить вершину u вместе с входящими в нее дугами. Уменьшить k на единицу.

4. Шаги 2 и 3 повторять до тех пор, пока все вершины не будут перенумерованы.

 

 

 

7.5.Сетевое планирование

Многие крупные работы (проекты) как правило, состоят из более мелких работ (операций). Некоторые из операций могут выполняться одновременно, другие - только последовательно. Например, при строительстве дома можно совместить во времени внутренние отделочные работы и работы по благоустройству территории, однако возводить стены можно только после закладки фундамента.

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

Для задания проекта необходима следующая информация:

1. Перечень всех операций проекта.

2. Время необходимое для выполнения каждой операции.

3. Перечни операций, непосредственно предшествующих каждой операции.

Каждый проект можно представить в виде ориентированного графа, в котором каждая операция соответствует некоторой дуге, при этом выполняется следующее правило: если некоторая операция представлена дугой (x,y), то в вершину x входят только дуги, представляющие операции, непосредственно предшествующие данной операции. Каждой дуге приписывается число равное времени выполнения соответствующей операции. При необходимости в граф вводятся фиктивные операции, т.е. дуги, не представляющие никакой операции (фиктивные дуги). Время выполнения фиктивной операции равно нулю. Граф, представляющий проект, называется сетевым графиком.

Вершины сетевого графика называют событиями. Говорят, что событие x произошло, если все операции непосредственно предшествующие операции соответствующей некоторой дуге (x,y) завершились.

В сетевом графике есть начальное событие, т.е. событие, соответствующее началу работы над проектом и конечное событие, т.е. событие, соответствующее окончанию работ над проектом.

Пример. Рассмотрим абстрактный проект, представленный в табл.7.2. Время операций в проекте не важно. Данному проекту соответствует сетевой график на рис.7.21.

 

Таблица 7.2

Информация о проекте

Операция	Непосредственно предшествующие операции
A	нет
B	A
C	A
D	A
E	B,C
F	B,C,D
G	E,F

 

Отметим, что сетевой график не может содержать контуров. Действительно, пусть в сетевом графике имеется контур (a,b),(b,c),...,(r,s),(s,a). Тогда событие a не может произойти, пока не произошло событие s, событие s не может произойти, пока не произошло событие r, и т.д. Очевидно, что в этом случае проект никогда не может быть завершен.

Поскольку сетевой график не содержит контуров, он может быть топологически отсортирован. Это упрощает алгоритмы расчета наиболее ранних и наиболее поздних сроков наступления событий, которые будут рассмотрены в разделах 7.5.1 и 7.5.2 соответственно.