Алгоритъм за търсене в дълбочина (Depth First Search)

Алгоритъмът за обхождане в дълбочина наред с това, че е неразделна част от някои по-сложни алгоритми, е основна идея при един от фундаменталните методи за решаване на изчерпващи задачи – търсене с връщане (backtracking).
Наименованието на алгоритъма идва от това, че при посещение на връх се стремим да се “спуснем” от него колкото може по-надолу.
За реализацията му е най-удобно да се изпозва рекурсивна функция, която може да се опише в няколко стъпки:

Разглежда се връх i.
Маркира се като посетен.
За всеки непосетен връх j се изпълнява стъпка 1.
Алгоритъмът завършва след като всички върхове на графа са посетени.

Ето как може да се реализира този алгоритъм със средствата на езика С++. Тук графът отново е представен чрез матрица на съседство. Въвеждат се двойки свързани върхове, като за край на въвеждане служат две нули. Обхождането става чрез рекурсивната функция dfs. Като помощен масив се използва масива used, който служи за маркиране на посетените върхове.

Ако за начален връх на обхождане се въведе връх с нoмер 6 обхождането се извършва както е показано на анимацията.

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n,v,used[101];
vector<int>a[101];

void dfs(int k)
{
  printf("%d ",k);
  for(int i=0; i<a[k].size(); i++)
  {
    if(used[a[k][i]]) continue;
    used[a[k][i]]=1;
    dfs(a[k][i]);
  }

}

int main()
{
  scanf("%d %d",&n,&v); /* Брой върхове на графа и   връх, от който да обхождаме*/
  int b,c;
  while(b!=0 || c!=0)
  {
    scanf("%d %d",&b,&c);
    a[b].push_back(c);
    a[c].push_back(b);
  }
  for (int i=0; i<n; i++)   sort(a[i].begin(),a[i].end());
  used[v]=1;
  dfs(v);
  return 0;
}