Поиск в ширину и глубину
Поиск в ширину
Поиск в ширину (BFS, Breadth-first search) — метод обхода и разметки вершин графа.
Поиск в ширину выполняется в следующем порядке:
Поиск в ширину реализуется с помощью структуры очередь. Для этого занесем в очередь исходную вершину. Затем будем работать, пока очередь не опустеет, таким образом: выберем элемент из очереди и добавим все смежные ему элементы, которые еще не использованы.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
Procedure BFS(v: integer); Var q: array[1..n] of integer; start, finish, i, j: integer; Begin fillchar(q, sizeof(q), 0); start := 0; finish := 0; inc(finish); q[finish] := v; marked[v] := true; while(start < finish) do begin inc(start); v := q[start]; {WriteLn(v);} For j := 1 to n do if (a[v, j] <> 0) and (not marked[j]) then begin inc(finish); q[finish] := j; marked[j] := true; end; end; End; |
Поиск в глубину
Поиск в глубину (Depth-first search, DFS) — один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой непройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них.
Пусть задан граф G = (V,E), где V — множество вершин графа, E — множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:
- Из множества всех белых вершин выберем любую вершину, обозначим её v1.
- Выполняем для неё процедуру DFS(v1).
- Перекрашиваем её в чёрный цвет.
- Повторяем шаги 1-3 до тех пор, пока множество белых вершин не пусто.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
const MAX_N = 10; var graph: array [1..MAX_N, 1..MAX_N] of boolean; visited: array [1..MAX_N] of boolean; procedure dfs(v: integer); var i: integer; begin visited[v] := true; for i := 1 to MAX_N do if graph[v, i] and not visited[i] then dfs(i); end; |
big_boss
| #
Согласен с Олегом, статья действительно интересная. Однако листая страницы поисковых систем наткнулся на сайт схожей тематики, где каждый изучен метод закрепляется программной реализацией в среде Delphi. Если тебя Олег интересует такой способ разработки программных продуктов преподаю ссылки на ресурс: http://www.mathros.net.ua. Надеюсь автор данного сайта не будет против.
Reply
tux
| #
Не будет 🙂
И даже сам с удовольствием почитает указанный вами сайт.
Reply