# Depth First Search algorithm in general terms

************************************************

Input :
Un weighted graph
Beginning vertex -v
Output :
The visited vertices.
Data structures used :Stack to store the vertices
************************************************

ALGORITHM:

1)Lable vertex v as reached.
2)Initialize S to be a stack with only v in it.
3)while S is not empty repeate through steps 4 , 5 & 6.
4)Delete a vertex w from the stack.
5)for all vertices u adjacent from w repeate through steps 6.
6)if u has not been labeled add u to the stack S , lable u as reached.

## 3 thoughts on “Depth First Search algorithm in general terms”

1. ryma says:

cool!!!.

2. /****************************************
APPLICATION : Depth First Search (DFS)
CODED BY : Ankit Pokhrel
COMPILED ON : Borland C++ Ver 5.02
DATE : 2010 – October – 12
****************************************/

#include
#include

struct Node //Structure to represent a Node or Vertices of a Graph
{
int status;
char data;
struct Node *next,*head; //Pointers to next node and Start
};

{
struct Node *next;
};

Node *New,*top; //Global Variables for New node and Pointer to Top
void create()
{
New = new Node; //Create a node
New -> status = false;
New -> next = NULL;
}

void CreateVertices(Node *&n,char Item) //Function to Create a Vertices of a Graph
{
if(n == NULL) //if first node
{
n = new Node; //Create a node
n -> data = Item; //Insert Data
n -> status = false;
n -> next = NULL;
top = n; //Update top
return;
}

create(); //Create a node
New -> data = Item; //Insert Item
top -> next = New; //Assign new node to next of top
top = New; //Update top
}

{
while(temp != NULL) //Until last
{
cout << "\nEnter Adjacents of " < data <> ch; //Scan Adjacent
a -> next = NULL;
if(flag == 0) //if first Adjacent
{
ptr = a;
flag++; //Increase flag
}

else
{
ptr = a;
}

tmp = n -> head; //from start
while(tmp != NULL) //Until end
{
if(tmp -> data == ch) //if node found
tmp = tmp -> next;
}
}while(ch != ‘0’);
temp = temp -> next;
}
}

void DFS(Node *n,char Item)
{
int top = -1;
char stack[30]; //Create a Stack
stack[++top] = Item; //Push starting Item
cout << Item <= 0) //until stack is empty
{
temp = n;
while(temp -> data != ch) //goto starting node
temp = temp -> next;
temp -> status = true; //update status

{
tmp = a -> next;
if(tmp -> status == false)
{
stack[++top] = tmp -> data; //save adjacents to stack
tmp -> status = true; //update status
}
}

ch = stack[top];
if(top != 0)
cout << stack[top] << ' '; //output top of stack
–top;
}
}

int main()
{
int m;
char ch;
Node *nd = NULL;
cout <> m;

cout << "\nEnter Vertices Name : "; //Input the name of Vertices
for(int i = 0;i > ch;
CreateVertices(nd,ch); //Create Vertices of a Graph
}

cout <> ch;
cout << "\nThe nodes reachable from " << ch << " : ";
DFS(nd,ch); //Depth First Traversal
getch();
}

OUTPUT
———
How Many Vertices? 9

Enter Vertices Name : A B C D E F G J K

Enter Link for each Vertices (0 as Last Input):
Enter Adjacents of A : F C B 0
Enter Adjacents of B : G C 0
Enter Adjacents of C : F 0
Enter Adjacents of D : C 0
Enter Adjacents of E : D C J 0
Enter Adjacents of F : D 0
Enter Adjacents of G : C E 0
Enter Adjacents of J : D K 0
Enter Adjacents of K : E G 0

Find nodes reachable from : J

The nodes reachable from J : J K G C F E D