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

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

end;


Рекурсията в този случай е изключена чрез идползване на стек. За лабота с него се използват процедури за добавяне в стека (push), за инициализиране на стека (stackinit) и функциите – за извличане от стека (pop) и stackempty, която връща стойност true, когато стека е празен.


Търсене в ширина


Методът Breadth First Search (BFS) е другият класически алгоритам за обхождане на граф. За неговата реализация е необходимо да се заменят операциите за работа със стек с операции за работа с опашка – процедурите put – за добавяне в опашката, queueinit – за инициализиране на опашката и функциите get – за извличане от опашката и queueempty, коята връща стойност true, когато опашката е празна.

Тук първо се обхождат върховете на разстояние 1 от началния връх, после на разстояние 2 от началния връх и т.н.

  1. procedure listBFS;

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

  7. repeat

  8. k:=get;

  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. put(t^.v); val[t^.v]:=-1;

  16. end;

  17. t:=t^.next;

  18. end;

  19. until queueempty;

  20. end;

  21. begin

  22. id:=0; queueinit;

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


Други реферати:
Образът на света, създаден от История славяноболгарская
Патриархалният човек през погледа на разказвача от повестта Преди да се родя
Преди да се родя
Основни теми и ключови думи в творчеството на Димчо Дебелянов
Паисий-Иван Вазов


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



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