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

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


Други реферати:
Организация на транспортно обслужване и параметри на транспортния процес на таксиметровите превози в гр.Бургас
Схема на краен усилвател на мощност
Стратегически риск мениджмънт. Отговорността на консултанта.
Тракийски светилища и гробници
Недко Дончов Каблешков


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



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