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

V:=G[U,i];

end;

Тем самым, мы получаем обработку дуги, связывающей вершины U и V для всех вершин, непосредственно связанных с U.

Для обработки ВСЕХ связей всех вершин можно использовать поиск в глубину (DFS - Depth-First Search):

for U:=1 to N do Color[U]:=WHITE;

for U:=1 to N do

if color[U]=WHITE then DFS(U);

Procedure DFS(U:longint);

var

j : longint;

begin

color[U]:=GRAY;

for j:=1 to kG[U] do DFS(G[U,j]);

end;

Здесь

Color[U] = цвет вершины

WHITE (константа=1) - белый, если мы еще не посещали эту вершину

GRAY (константа=2) - серый, если мы посещали данную вершину

DFS(U) - рекурсивная процедура, которая вызывает себя для всех вершин, потомков данной вершины.

То есть, для обеспечения поиска в глубину на заданном графе G[1..N,1..M] с количествами дуг из вершин G[1..N], вначале мы устанавливаем всем вершинам цвет WHITE, а затем для всех вершин, которые еще не посещались (Color[G[U,j]]=WHITE) вызываем рекурсивную процедуру DFS.

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

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

Procedure DFS(U:longint);

var

j : longint;

begin

color[U]:=GRAY;

for j:=1 to kG[U] do

if color[G[U,j]]=WHITE then DFS(G[U,j]);