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

readln(n, e);

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;

  3. procedure visit(k:integer);

  4. var t:link;

  5. begin

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

  7. t:=adj[k];

  8. while t<>z do

  9. begin


Други реферати:
Форд и Дженерал Мотърс
Казус по основи на управлението
Икономическата теория и устойчивото развитие
Изследване и развитие на фирма АДС
Казус по публична администрация


Изтегли реферата



Казус по публична администрация - Facebook Image
Сайтът се поддържа от DH Studio | pomagalo1.com © 2012 | Общи условия