ВУЗ:
Составители:
Рубрика:
Ниже на рисунке указан порядок прохождения вершин при по-
иске в ширину для графа из примера 11.1, а также приведено со-
держимое массивов queue, new, и prev .
2
1
3 2
4 6
6 3 2
5 4 6
8 7 5 4
queue
5 (6)
4 (5)
8 (8)
6 (4)
3 (3)
7 (7)
2 (2)
1 (1)
prev
new
2 1 3 4 5 6 7 8
T
F
2
T
F
3
T
F
1
T
F
5
T
F
6
T
F
4
T
F
7
T
F
8
1 31 3 1 6 6
Замечание.
Содержимое prev[u] содержит вершину, из которой
мы попали в u. Таким образом, мы имеем возможность определить
кратчайший путь от начальной до нужной вершины.
Алгоритмы поиска в глубину и в ширину могут быть легко мо-
дифицированы для поиска компонентов связности графа, а также
для нахождения покрывающего дерева графа. Ниже приведена
процедура построения покрывающего дерева графа G=(V,E),
V={v
1
,…,v
n
}, основанная на алгоритме поиска в глубину. Исполь-
зуем ранее введенные обозначения и пусть T - массив ветвей ис-
комого дерева.
procedure WGD[v]- процедура поиска покрывающего дерева
графа методом поиска в глубину (depth first search), начиная с
вершины v.
begin
stack:=0; stack
←
v; T:=0;
new[v]:=false;
while stack
≠
0 do
44
Страницы
- « первая
- ‹ предыдущая
- …
- 42
- 43
- 44
- 45
- 46
- …
- следующая ›
- последняя »
