ВУЗ:
Составители:
Рубрика:
ветить на вопрос: достижима ли вершина d из вершины v, то есть,
существует ли путь из v в d. Если исходный граф неориентирован-
ный, то для ответа на данный вопрос достаточно определить при-
надлежат ли вершины v и d одному компоненту связности. Выде-
лить связные компоненты можно с помощью алгоритма Краскала.
Если после завершения работы алгоритма Краскала вершины v и d
принадлежат разным деревьям покрывающего леса (разным буке-
там – в терминах, используемых при формулировке алгоритма
Краскала), то пути из вершины v в вершину d не существует, в
противном случае путь существует.
Для ориентированного графа такой алгоритм непригоден. Для
ответа на вопрос достижима ли вершина d из вершины v, необхо-
димо организовать обход вершин графа, начиная из вершины v.
Если во время обхода мы встретим вершину d, следовательно,
вершина d достижима из вершины v, в противном случае d из v не
достижима.
Существует два способа организации обхода: поиск в глубину и
поиск в ширину. Просмотр всех вершин графа G=(V,E),
V={v
1
,…,v
n
} осуществляется так, что каждая вершина рассматрива-
ется один раз.
Поиск в глубину
Обозначения: new[1..n] - массив булевых переменных,
⎩
⎨
⎧
=
алась;просматрив если
алась,просматрив не если
v,false
v,true
]v[new
U[1…n] -массив указателей на списки инцидентно-
сти вершин графа;
stack -стек (LIFO - last-in-first-out) емкости n.
Алгоритм поиска в глубину
(в круглых скобках даны коммен-
тарии).
procedure DFS[v]- процедура поиска в глубину (depth first
search), начиная с вершины v.
begin
stack:=0; stack
←
v; рассмотреть v;
new[v]:=false;
while stack
≠
0 do
begin
t:= top(stack); (верхний элемент стека)
40
if U[t]=nil then b:=false
Страницы
- « первая
- ‹ предыдущая
- …
- 38
- 39
- 40
- 41
- 42
- …
- следующая ›
- последняя »
