Depth First Traversal

Depth first traversal, also known as depth first search or DFS, is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

• C#
• VB.Net
• C
• C++

									/*****Please include following header files*****/
// stdio.h
/***********************************************/

typedef struct vertex_struct {
	char Label;
	bool Visited;
} Vertex;

int _top = -1;
int _vertexCount = 0;

void Push(int* stack, int item) {
	stack[++_top] = item;
}

int Pop(int* stack) {
	return stack[_top--];
}

int Peek(int* stack) {
	return stack[_top];
}

bool IsStackEmpty() {
	return _top == -1;
}

int** Create2DArray(int rowCount, int colCount) {
	int** arr = new int*[rowCount];

	for (int i = 0; i < rowCount; ++i)
		arr[i] = new int[colCount];

	return arr;
}

void AddVertex(Vertex** arrVertices, char label) {
	Vertex* vertex = new Vertex();
	vertex->Label = label;
	vertex->Visited = false;
	arrVertices[_vertexCount++] = vertex;
}

void AddEdge(int** adjacencyMatrix, int start, int end) {
	adjacencyMatrix[start][end] = 1;
	adjacencyMatrix[end][start] = 1;
}

void DisplayVertex(Vertex** arrVertices, int vertexIndex) {
	printf("%c ", arrVertices[vertexIndex]->Label);
}

int GetAdjacentUnvisitedVertex(Vertex** arrVertices, int** adjacencyMatrix, int vertexIndex) {
	for (int i = 0; i < _vertexCount; ++i) {
		if (adjacencyMatrix[vertexIndex][i] == 1 && arrVertices[i]->Visited == false) {
			return i;
		}
	}
	return -1;
}

void DepthFirstSearch(Vertex** arrVertices, int** adjacencyMatrix, int* stack) {
	arrVertices[0]->Visited = true;
	DisplayVertex(arrVertices, 0);
	Push(stack, 0);

	while (!IsStackEmpty()) {
		int unvisitedVertex = GetAdjacentUnvisitedVertex(arrVertices, adjacencyMatrix, Peek(stack));

		if (unvisitedVertex == -1) {
			Pop(stack);
		}
		else {
			arrVertices[unvisitedVertex]->Visited = true;
			DisplayVertex(arrVertices, unvisitedVertex);
			Push(stack, unvisitedVertex);
		}
	}

	for (int i = 0; i < _vertexCount; ++i) {
		arrVertices[i]->Visited = false;
	}
}
								

Example

									int max = 5;
int* stack = new int[max];
Vertex** arrVertices = new Vertex*[max];
int** adjacencyMatrix = Create2DArray(max, max);

for (int i = 0; i < max; ++i)
	for (int j = 0; j < max; ++j)
		adjacencyMatrix[i][j] = 0;

AddVertex(arrVertices, 'S');
AddVertex(arrVertices, 'A');
AddVertex(arrVertices, 'B');
AddVertex(arrVertices, 'C');
AddVertex(arrVertices, 'D');

AddEdge(adjacencyMatrix, 0, 1);
AddEdge(adjacencyMatrix, 0, 2);
AddEdge(adjacencyMatrix, 0, 3);
AddEdge(adjacencyMatrix, 1, 4);
AddEdge(adjacencyMatrix, 2, 4);
AddEdge(adjacencyMatrix, 3, 4);

printf("Depth First Search: ");
DepthFirstSearch(arrVertices, adjacencyMatrix, stack);
								

Output

									Depth First Search: S A D B C