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

if val[t^.v]=0 then visit(t^.v);

t:=t^.next;

end;

end;

begin

id:=0;

for k:=1 to v do val[k]:=0;

for k:=1 to v do

if val[k]=0 then visit(k);

end;


Времето, необходимо за изпълнение на DFS за граф, представен чрез списъци е пропорционално на n+e, а за граф, представен чрез матрица на съседство – n2.

Нерекурсивен DFS:

  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. push(k);

  7. repeat

  8. k:=pop;

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

  10. t:=adj[k];

  11. while t<>z do

  12. begin

  13. if val[t^.v] = 0 then

  14. begin

  15. push(t^.v); val[t^.v]:=-1;

  16. end;

  17. t:=t^.next;

  18. end;

  19. until stackempty;

  20. end;

  21. begin

  22. id:=0; stackinit;

  23. for k:=1 to n do val[k]:=0;

  24. for k:=1 to n do


Други реферати:
Хиперемезис гравидарум.
Хора с увреждания.
Хранене и периоди в детската възраст.
Mercedes Benz.
SHELL


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



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