Программирование на языке Pascal

       

Обратный обход произвольного связного графа


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

procedure postorder_graph(v:byte); var i: integer; begin posesh[v]:=1; {текущая вершина v стала посещенной} for i:=1 to n do if (posesh[i]=0)and(sm[v,i]=1) {есть ребро из текущей вершины v в еще не помеченную вершину i} then postorder_graph(i); inc(k); mark[v]:=k; {текущей вершине v присвоен порядковый номер} end;

begin ... k:=0; postorder_graph(start); {вызов из тела программы} ... end.



Содержание раздела