Algoritmul Depth-First

Aspecte teoretice:

Depth-first search (DFS) este un algoritm căutare a arborelui, structurii arborelui, sau a grafului. Formal, DFS reprezintă o căutare care evoluează prin expansiunea la primul vârf „fiu” a arborelui ce ia naştere pe măsură ce se coboară în adâncime, până în momentul în care vârful „ţintă” este descoperit sau până când se întâlneşte un vârf care nu are „fii”. La pasul următor, căutarea se reia (backtracking), revenind la nodul cel mai recent vizitat, însă pentru care explorarea nu este încheiată. Într-o implementare nerecursivă, toate vârfurile recent vizitate sunt adăugate într-o stivă de tipul LIFO (Last In First Out), în scopul explorării acestora. Complexitatea în spaţiu a DFS este cu mult mai mică decât cea a BFS (Breadth-First Search).
De asemenea se pretează mult mai bine metodelor euristice de alegere a ramurilor asemănătoare. Complexitatea în timp a ambilor algoritmi este proporţională cu numărul vârfurilor plus numărul muchiilor grafului corespunzător (O(V + E )).
Căutarea în adâncime se poate folosi şi la ordonarea liniară a vârfurilor grafului (sau arborelui). Există trei astfel de posibilităţi:
■ O preordine reprezintă o listare a vârfurilor în ordinea în care au fost vizitaţi prin intermediul algoritmului căutării în adâncime. Aceasta este o modalitate naturală şi compactă de descriere a progresului căutării. O preordine a unei expresii arbore este ceea ce numim expresie în notaţia Polonezǎ.
■ O postordine reprezintă o listare în care cel din urmă vârf vizitat este primul element al listei. O postordine a unui expresii arbore este de fapt expresia în oglindă a expresiei în notaţie Polonezǎ.
■ O postordine inversată (în oglindă) este, de fapt, reversul postordinii, i.e. o listare a vârfurilor în ordinea inversă a celei mai recente vizite a vârfurilor in cauză. În căutarea unui arbore, postordinea inversată coincide cu preordinea, însă, în general, diferă atunci când se caută un graf.

Cod Sursa C++

// DepthFirstCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
 
using namespace std;
 
int a[20][20], n, m, viz[100], gasit;
 
void dfmr(int nod)
{
	cout << nod << " ";
	viz[nod] = 1;
	for (int k = 1; k <= n; k++)
	if (a[nod][k] == 1 && viz[k] == 0)
		dfmr(k);
}
 
void main()
{
	int x, y, j;
	cout << "numarul de noduri: ";
	cin >> n;
	cout << "numarul de muchii: ";
	cin >> m;
	for (int i = 1; i <= m; i++)
	{
		cout << "nodul sursa: ";
		cin >> x;
		cout << "nodul destinatie: ";
		cin >> y;
		a[x][y] = 1;
	}
	cout << endl << "matricea de adiacente" << endl;
	for (int i = 1; i <= n; i++)
	{
		for (j = 1; j <= n; j++)
			cout << a[i][j] << " ";
		cout << endl;
	}
	cout << endl << "parcurgere in adancime incepand de la varful 1" << endl;
	dfmr(1);
	system("pause");
}

Rezultat: