Графи математика

new(z); z^.next:=z;

for j:=1 to n do adz[j]:=z;

for j:=1 to e do

begin

readln(v, w);

new(t); t^.v:=w; t^.next:=adj[v]; adj[v]:=t;

end;

end.

За неориентиран граф освен дъгата (v, w) трябва да се прибави и обратната дъга (w, v). За целта се прибавя след ред 15:

new(t); t^.v:=v; t^.next:=adj[w]; adj[w]:=t;

Тъй като възлите, свързани с даден възел се записват в съответствие с реда на въвеждане на дъгите, то съществуват различни варианти на такова представяне на графа.

Често се налага да се отговори на някои от следните въпроси: Свързан ли е графът? Ако не е, колко свързани компоненти има? Има ли цикли? Да се изведат циклите. Има ли път между два върха? Какъв е минималния път между два върха?

Ще разгледаме два метода, които дават отговор на тези и други въпроси.

Търсене в дълбочина

При метода Depth First Search (DFS) се извършва обхождане на графа, така че всеки възел бива “посетен” и се минава по всяка дъга. При него преди к – тата стъпка сме намерили път (v1, v2, …, vk) и се опитваме да намерим връх vk+1 свързан с vk и все още не посетен. Ако има такъв, то го отбелязваме като посетен, добавяме към пътя върха vk+1 и се извикваме рекурсивно за новия път. Ако не намерим връх vk+1 отговарящ на условията то се връщаме към предната стъпка и повтаряме същото. Метода се използва за неориентирани графи.

На всеки от върховете в случая се присвоява стойност по реда, в който сме ги посещавали.

Търсене в дълбочина за граф, представен чрез списъци:

1. Procedure listDFS;

2. Vartext-align: left" lang="bg-BG">val:array [1..maxN] of integer;

4. procedure visit(k:integer);

5. var t:link;

6. begin

7. id:=id+1; val[k]:=id;

8. t:=adj[k];

9. while t<>z do

10. begin