2015-08-21
285
2. помітити вершину v як відвідану
3. для кожної не відвіданої вершини и, суміжною з вершиною v
dfs(u);
Все
Все.
Алгоритм пошуку в глибину не повністю задає порядок обходу вершин, суміжних з даною. Наприклад, суміжні вершини можна обходити в порядку зростання їх значення.
Ітеративний алгоритм обходу графу в глибину з використанням стеку:
Dfs(v: вершина)
s:Stack;
s.CreateStack;
s.push(v);
Помітити вершину v як відвідану;
Поки (!s.isEmpty) //поки стек не порожній
Begin
If (у вершини графу на вершині стеку не залишилось суміжних невідвіданих вершин)
s.pop;
Else
Begin
вибрати не відвідану вершину и, суміжну з вершиною на вершині стеку;
s.push(u);
Помітити вершину и як відвідану
End
End.
Приклад роботи цього алгоритму наведено на мал.2.
Завдання на роботу.
Написати програму обходу графу в глибину:
| № п/п | Кількість вершин | Суміжні вершини |
| (1,4),(2,4),(3,4),(4,5),(6,5),(7,5),(8,7),(9,7),(10,7),(13,9),(14,9),(11,10),(12,10) | ||
| (2,1),(3,1),(4,1),(5,1),(6,3),(7,3),(8,4),(9,4),(10,5),(11,5),(12,5),(13,6),(14,6),(15,8) | ||
| (1,7),(2,7),(6,7),(5,7),(3,6),(4,6),(7,8),(16,8),(9,16),(10,16),(11,8),(12,8),(15,8),(13,15),(14,15) | ||
| (1,5),(2,5),(3,5),(5,4),(6,4),(7,4) | ||
| (1,2),(1,3),(4,2),(5,2),(6,3),(7,3),(8,7) | ||
| (1,4),(2,4),(3,4),(4,5),(6,5),(7,5),(9,7),(8,7) | ||
| (1,4),(2,4),(4,5),(3,5),(6,5),(7,5),(9,7),(8,7),(10,7) | ||
| (2,1),(3,1),(4,2),(5,2),(6,3),(7,3),(8,5),(9,5),(11,7),(10,7) | ||
| (1,7),(2,7),(3,10),(4,10),(10,8),(11,8),(12,8),(7,8),(8,9),(6,9),(5,9) | ||
| (1,7),(2,7),(5,10),(4,10),(12,11),(13,11),(6,9),(5,9),(7,8),(8,9),(10,8),(11,8) |
Контрольні питання.
|
|
|
1. Поняття обходу графу.
2. Суть алгоритму обходу в глибину.
3. Рекурсивний алгоритм обходу в глибину.
4. Ітеративний алгоритм обходу в глибину (з використанням стеку).
