Поиск в глубину в графе используется в основном для поиска количества компонентов связности, а также для поиска циклов в графе.
Что делает поиск в глубину(DFS)? Он проходит вершины в графе, смежные с изначальной и помечает пройденные. Вот и все.
А теперь код:
Примечание: не забудьте заполнить массив marked(помеченные) False'ами.
Процедура помечает вершину(v), затем проходится по всем вершинам и смотрит, если вершина не помечена и смежна с данной(v), то запускается от нее.
Матрица смежности(a) в процедуру не передается, так как я использовал Делфи. В Паскале не забудьте это сделать.
Что делает поиск в глубину(DFS)? Он проходит вершины в графе, смежные с изначальной и помечает пройденные. Вот и все.
А теперь код:
- Код:
Procedure DFS(v: integer)// v это текущая вершина.
Var i: integer;
Begin
marked[v] := true;
For i := 1 to n do
if (a[v, i] = 1) and (not marked[i]) then dfs(i); //a - это матрица смежности графа(1 - есть ребро, 0 - нет).
End;
Примечание: не забудьте заполнить массив marked(помеченные) False'ами.
Процедура помечает вершину(v), затем проходится по всем вершинам и смотрит, если вершина не помечена и смежна с данной(v), то запускается от нее.
Матрица смежности(a) в процедуру не передается, так как я использовал Делфи. В Паскале не забудьте это сделать.
Ср Окт 12, 2016 2:43 am автор SeriousPasha
» требуется несколько JS разработчиков
Пт Окт 07, 2016 10:19 pm автор mrktwn1
» Защита приложения от взлома
Чт Июн 18, 2015 10:28 pm автор stradi
» Ищите программиста или дизайнера?
Пт Мар 27, 2015 6:25 am автор фриланс
» Создание и продвижение сайтов, их развитие.
Ср Мар 25, 2015 12:40 am автор asdfghhgfdsa
» Исходники для студентов + скайп-консультации,помощь в написании программ
Вт Окт 07, 2014 11:25 pm автор Horpion
» IT- технологии для развития бизнеса
Пн Июн 23, 2014 6:11 pm автор dvos12
» Стенли Кубрик "С Широко закрытыми Глазами"
Чт Июн 12, 2014 2:01 am автор Vertuozzz
» Каталог популярных хостинг компаний
Сб Май 10, 2014 7:18 pm автор naik