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++

									public struct Vertex
{
	public char Label;
	public bool Visited;
}

private static int _top = -1;
private static int _vertexCount = 0;

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

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

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

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

public static void AddVertex(Vertex[] arrVertices, char label)
{
	Vertex vertex = new Vertex();
	vertex.Label = label;
	vertex.Visited = false;
	arrVertices[_vertexCount++] = vertex;
}

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

private static void DisplayVertex(Vertex[] arrVertices, int vertexIndex)
{
	Console.Write(arrVertices[vertexIndex].Label + " ");
}

private static 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;
}

public static 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 = new int[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);

Console.Write("Depth First Search: ");
DepthFirstSearch(arrVertices, adjacencyMatrix, stack);
								

Output

									Depth First Search: S A D B C