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

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;

4. procedure visit(k:integer);

5. var t:link;

6. begin

7. put(k);

8. repeat

9. k:=get;

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

11. t:=adj[k];

12. while t<>z do

13. begin

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

15. begin

16. put(t^.v); val[t^.v]:=-1;

17. end;

18. t:=t^.next;

19. end;

20. until queueempty;

21. end;

23. begin

24. id:=0; queueinit;

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