Графи математика
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 отговарящ на условията то се връщаме към предната стъпка и повтаряме същото. Метода се използва за неориентирани графи.
На всеки от върховете в случая се присвоява стойност по реда, в който сме ги посещавали.
Търсене в дълбочина за граф, представен чрез списъци:
-
Procedure listDFS;
-
Vartext-align: left" lang="bg-BG">val:array [1..maxN] of integer;
-
procedure visit(k:integer);
-
var t:link;
-
begin
-
id:=id+1; val[k]:=id;
-
t:=adj[k];
-
while t<>z do
-
begin
Други реферати:
Изследване на елементите на обкръжаващата среда на Плевен Булгартабак АД
Какво знаем за основите на училищното управление
PR-програма в библиотеките
Кога е ефективен PR
Връзки с обществеността
Изтегли реферата