Лекции по дискретной математике. Ч.II. Комбинаторика, разостные уравнения, алгоритмы на графах. Гайдамака Ю.В - 43 стр.

UptoLike

ВУЗ: 

РУДН | Москва

Составители: 

Рубрика: 

Замечание.
Перечеркивание вершины на рисунке обозначает
удаление соответствующей вершины из стека (это происходит в
случае, когда в стек попадает уже рассмотренная ранее вершина).
Ниже приведено содержимое массива new. Верхняя строка дает
исходное состояние. В нижней строке указан порядок изменения
состояния элементов массива (ср. с рисунком графа).
new
2 1
3
4
5
6
7
8
T
(true)
F
(false)
1
T
F
2
T
F
4
T
F
5
T
F
6
T
F
3
T
F
7
T
F
8
Поиск в ширину в графе
Вместо стека в данном алгоритме используется очередь.
Обозначения: prev[1..n] - вспомогательный массив;
queue - очередь (FIFO - first-in-first-out) емкости n.
Алгоритм поиска в ширину
(в круглых скобках даны коммента-
рии).
procedure BFS(v)- процедура поиска в ширину (breadth first
search), начиная с вершины v
begin
queue:=0; queue
←
v; new[v]:=false;
while queue
≠
0 do
begin
p
←
queue; (извлечь из очереди вершину), рассмотреть p;
while U[p}
≠
nil do
begin
if new [U[p]
↑
.dat] then
begin
queue
←
U[p]
↑
.dat; new[U[p]
↑
.dat]:=false;
prev[U[p]
↑
.dat]:=p;
end;
U[p]:=U[p]
↑
.next;
end;
end;
end;
43

Страницы