Курсовая работа: Алгоритмы на графах. Кратчайшие расстояния на графах

Если по условиям задачи требуется каждую дугу использовать не более одного раза, то можно ввести расцветку дуг:

Color[1..N,1..M] - со значениями FREE или DONE где, как и ранее

N - число вершин в графе,

M - максимально возможное число ребер (дуг) у одной вершины графа.

А процедура DFS формирования маршрутов так, что бы каждая дуга использовалась в маршруте не более одного раза, будет выглядеть следующим образом:

procedure DFS(v:byte);

var j : byte;

begin

for j:=1 to kG[v] do

if (color[v,j]=FREE)

then

begin

color[v,j]:=DONE;

DFS(G[v,j]);

color[v,j]:=FREE;

end;

end;

Здесь вводятся пометки на дуги

Color[v,j] = FREE,

если дуга еще не обработана, и DONE, если она включена в текущий путь.

Если в задаче требуется вывести найденный путь, то для его хранения заводится специальный массив SLED [1..Q], где Q - максимальное количество ребер в пути и вершины текущего пути заносятся в этот массив и удаляются из него в процессе обхода графа:

procedure DFS(v:byte);

var j : byte;

begin

for j:=1 to kG[v] do

begin

inc(ks); sled[ks]:=G[v,j];

DFS(G[v,j]);

dec(ks);