|
|
|
Същността на алгоритъма е да обхожда напред (в дълбочина), докато е възможно, а когато не е, се връща назад. При DFS, всеки връх има три основни състояния:  - върха не е посетен - върха се процесира от DFS - DFS е приключил с процесирането на върхаВ повечето случаи две състояния (посетен и непосетен) са достатъчни, но тък разглеждаме общия случай Първоначално всички върхове са непосетени (бели). DFS започва от произволен връх и се движи както следва: 1. Отбележи връх u като посетен (сив) 2. За всяко ребро (u,v), където u е непосетен, изпълни DFS за u рекурсивно. 3. Отбележи връх u като черен и се върни. Пример за обхождане на граф с DFS, започвайки от връх номер 1: Начален граф.  Отбележи връх 1 в сиво.  Има ребро (1,4) и връх 4 е непосетен. Отиди там.  Отбележи връх 4 в сиво.  Има ребро (4,2) и връх 2 е непосетен. Отиди там.  Отбележи връх 2 в сиво.  Има ребро (2,5) и връх 5 е непосетен. Отиди там.  Отбележи връх 5 в сиво.  Има ребро (5,3) и връх 3 е непосетен. Отиди там.  Отбележи връх 3 в сиво.  Няма повече ребра излизащи от връх 3, отбележи го в черно и се върни към връх 5.  Има ребро (5,4), но връх 4 е посетен.  Няма повече ребра излизащи от връх 5, отбележи го в черно и се върни към връх 2.  Няма повече ребра излизащи от връх 2, отбележи го в черно и се върни към връх 4.  Има ребро (4,5), но връх 5 е черен.  Няма повече ребра излизащи от връх 4, отбележи го в черно и се върни към връх 1.  Няма повече ребра излизащи от връх 1, отбележи го в черно. DFS приключва.  Източник: www.algolist.net |
|
|
