Depth First Search

algorithm.md

###Depth First Search [DFS] - A Graph traversal algorithm

Starting from root, this algorithm goes on exploring every node in a preorder traversal pattern.

Although it closely resembles with preorder traversal, there is a slight difference. Each nodes are visited only once. It goes on exploring till the leaves appear and then backtrace to neighbour and then again other siblings. It keeps a record of whether a node has been visited or not. Since it's operation is highly stack dependent, the most easy way to achieve this is by recursion.

DFS(Vertex V):
	Mark V as VISITED
	FOR EACH neighbour U of V:
		IF U NOT VISITED:
			DFS(U)
		END IF
	END FOR
END DFS

The complexity of DFS Traversal runs in the order of O(|V| + |E|), where |V| and |E| represents the number of vertices and edges in the graph. It wraps up in a space complexity of O(|V|) at max.

dfs.c

/*
	DEPTH FIRST SEARCH
	Recursive Approach
	** for TURBO C, remove // from commented statements
*/

#include<stdio.h>
//#include<conio.h>

#define V 8 // no. of vertices in graph

/////////////////////////////////////////////
//	Adjacency Matrix for a Sample Graph
/////////////////////////////////////////////
int GRAPH[][V]= {
//	       A  B  C  D  E  F  G  H  
/*	A */ { 0, 1, 1, 1, 0, 0, 0, 0 },
/*	B */ { 1, 0, 0, 0, 1, 1, 0, 0 },
/*	C */ { 1, 0, 0, 1, 0, 0, 0, 0 },
/*	D */ { 1, 0, 0, 1, 0, 0, 1, 0 },
/*	E */ { 0, 1, 1, 1, 0, 0, 0, 1 },
/*	F */ { 0, 1, 0, 0, 0, 0, 0, 1 },
/*	G */ { 0, 0, 0, 1, 0, 0, 0, 1 },
/*	H */ { 0, 0, 0, 0, 1, 1, 1, 0 }
};
#define GRAPH_ROOT 0
/////////////////////////////////////////////

/////////////////////////////////////////////
// to keep track of visited node
/////////////////////////////////////////////
int VERTEX_STATUS[V];
#define VISITED 1
#define NOT_VISITED 0
/////////////////////////////////////////////

void DFS(int v){
	
	int u;
	VERTEX_STATUS[v] = VISITED;
	printf("Visited V%d\n" , v);
	for(u = 0; u < V; u++){

		// check for an edge between u and v
		if(GRAPH[u][v] == 1){
			// check if this has been visited already
			if(VERTEX_STATUS[u] == NOT_VISITED){
				DFS(u);
			}
		}
	}
}

int main(){
	int v;
	//clrscr();

	for(v = 0; v < V; v++){
		// set all vertices to NOT_VISITED
		VERTEX_STATUS[v] = NOT_VISITED;
	}

	printf("\nDFS Traversal ::\n");
	DFS(GRAPH_ROOT);

	//getch();
	return 0;
}

DFS.java

/*
	DEPTH FIRST SEARCH
	Recursive Approach
	Save File as DFS.java
*/

public class DFS{

	private static final int V = 8;

	/////////////////////////////////////////////
	//	Adjacency Matrix for a Sample Graph
	/////////////////////////////////////////////
	private static final int[][] GRAPH = {
	//	       A  B  C  D  E  F  G  H  
	/*	A */ { 0, 1, 1, 1, 0, 0, 0, 0 },
	/*	B */ { 1, 0, 0, 0, 1, 1, 0, 0 },
	/*	C */ { 1, 0, 0, 1, 0, 0, 0, 0 },
	/*	D */ { 1, 0, 0, 1, 0, 0, 1, 0 },
	/*	E */ { 0, 1, 1, 1, 0, 0, 0, 1 },
	/*	F */ { 0, 1, 0, 0, 0, 0, 0, 1 },
	/*	G */ { 0, 0, 0, 1, 0, 0, 0, 1 },
	/*	H */ { 0, 0, 0, 0, 1, 1, 1, 0 }
	};
	private static final int GRAPH_ROOT = 0;
	/////////////////////////////////////////////

	/////////////////////////////////////////////
	// to keep track of visited node
	/////////////////////////////////////////////
	private static boolean[] VERTEX_VISITED = new boolean[V];
	/////////////////////////////////////////////
	
	public static void DFS(int v){

		VERTEX_VISITED[v] = true;
		System.out.println("Visited V" + v);
		
		for(int u = 0; u < V; u++){

			// check for an edge between u and v
			if(GRAPH[u][v] == 1){
				// check if this has been visited already
				if(!VERTEX_VISITED[u]){
					DFS(u);
				}
			}
		}
	}

	public static void main(String s[]){

		for(int v = 0; v < V; v++){
			// set all vertices to NOT_VISITED
			VERTEX_VISITED[v] = false;
		}

		System.out.println("\nDFS Traversal ::\n");
		DFS(GRAPH_ROOT);
	}
}