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.

/****************************************
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 Adjacent *adj; //Pointer to Adjacent node
};

struct Adjacent //Structure to represent Adjacent node of a Graph
{
struct Node *next;
struct Adjacent *adj; //Pointer for next Adjacent
};

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;
New -> adj = 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;
n -> adj = NULL;
n -> head = n; //Initialize head
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
}

void LinkVertices(Node *&n)
{
Adjacent *a,*ptr;
cout < head,*tmp;
while(temp != NULL) //Until last
{
cout << "\nEnter Adjacents of " < data <> ch; //Scan Adjacent
a = new Adjacent; //Create an Adjacent
a -> adj = NULL;
a -> next = NULL;
if(flag == 0) //if first Adjacent
{
temp -> adj = a;
ptr = a;
flag++; //Increase flag
}

else
{
ptr -> adj = a;
ptr = a;
}

tmp = n -> head; //from start
while(tmp != NULL) //Until end
{
if(tmp -> data == ch) //if node found
a -> next = tmp; //Link adjacent
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

Adjacent *a = temp -> adj;
while(a -> adj != NULL)
{
tmp = a -> next;
if(tmp -> status == false)
{
stack[++top] = tmp -> data; //save adjacents to stack
tmp -> status = true; //update status
}
a = a -> adj; //goto next adjacent
}

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
}

LinkVertices(nd); //Link the 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

If the code doesn't work, please replace the single quotes and double quotes(Actually these are not proper single and double quotes) in the code with single quotes and double quotes using your keyboard..

cool!!!.

/****************************************

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 Adjacent *adj; //Pointer to Adjacent node

};

struct Adjacent //Structure to represent Adjacent node of a Graph

{

struct Node *next;

struct Adjacent *adj; //Pointer for next Adjacent

};

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;

New -> adj = 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;

n -> adj = NULL;

n -> head = n; //Initialize head

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

}

void LinkVertices(Node *&n)

{

Adjacent *a,*ptr;

cout < head,*tmp;

while(temp != NULL) //Until last

{

cout << "\nEnter Adjacents of " < data <> ch; //Scan Adjacent

a = new Adjacent; //Create an Adjacent

a -> adj = NULL;

a -> next = NULL;

if(flag == 0) //if first Adjacent

{

temp -> adj = a;

ptr = a;

flag++; //Increase flag

}

else

{

ptr -> adj = a;

ptr = a;

}

tmp = n -> head; //from start

while(tmp != NULL) //Until end

{

if(tmp -> data == ch) //if node found

a -> next = tmp; //Link adjacent

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

Adjacent *a = temp -> adj;

while(a -> adj != NULL)

{

tmp = a -> next;

if(tmp -> status == false)

{

stack[++top] = tmp -> data; //save adjacents to stack

tmp -> status = true; //update status

}

a = a -> adj; //goto next adjacent

}

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

}

LinkVertices(nd); //Link the 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