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

       

Прямой обход произвольного связного графа


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

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

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



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