Write a program in c to implement the depth first traversal?

Answer 1

#include <iostream.h>

#include <conio.h>

class graph

{

private:int n;

int **a;

int *reach;

int *pos;

public:graph(int k=10);

void create();

void dfs();

void dfs(int v,int label);

int begin(int v);

int nextvert(int v);

};

void graph::graph(int k)

{

n=k;

a=new int *[n+1];

reach=new int[n+1];

pos=new int [n+1];

for(int i=1;i<=n;i++)

pos[i]=0;

for(int j=1;j<=n;j++)

a[j]=new int[n+1];

}

void graph::create()

{

for(int i=1;i<=n;i++)

{

cout<<"Enter the "<<i<<"th row of matrix a:

";

for(int j=1;j<=n;j++)

cin>>a[i][j];

}

for(int k=1;k<=n;k++)

reach[k]=0;

}

void graph::dfs()

{

int label=0;

for(int i=1;i<=n;i++)

if(!reach[i])

{

label++;

dfs(i,label);

}

cout<<"

The contents of the reach array is:

;

for(int j=1;j<=n;j++)

cout<<reach[j]<<" ";

}

void graph::dfs(int v,int label)

{

cout<<v<<" ";

reach[v]=label;

int u=begin(v);

while(u)

{

if(!reach[u])

dfs(u,label);

u=nextvert(v);

}

}

int graph::begin(int v)

{

if((v<1)&&(v>n))

cout<<"Bad input

";

else

for(int i=1;i<=n;i++)

if(a[v][i]==1)

{

pos[v]=i;

return i;

}

return 0;

}

int graph::nextvert(int v)

{

if((v<1)&&(v>n))

cout<<"Bad input

";

else

for(int i=pos[v]+1;i<=n;i++)

if(a[v][i]==1)

{

pos[v]=i;

return i;

}

return 0;

}

void main()

{

clrscr();

int x;

cout<<"Enter the no of vertices:

";

cin>>x;

graph g(x);

g.create();

cout<<"dfs is.....";

g.dfs();

getch();

}

Answer 2

#include <stdio.h>

typedef struct node {

int value;

struct node *right;

struct node *left;

} mynode;

mynode *root;

add_node(int value);

void levelOrderTraversal(mynode *root);

int main(int argc, char* argv[]) {

root = NULL;

add_node(5);

add_node(1);

add_node(-20);

add_node(100);

add_node(23);

add_node(67);

add_node(13);

printf("\n\n\nLEVEL ORDER TRAVERSAL\n\n");

levelOrderTraversal(root);

getch();

}

// Function to add a new node...

add_node(int value) {

mynode *prev, *cur, *temp;

temp = malloc(sizeof(mynode));

temp->value = value;

temp->right = NULL;

temp->left = NULL;

if(root == NULL) {

printf("\nCreating the root..\n");

root = temp;

return;

}

prev = NULL;

cur = root;

while(cur != NULL) {

prev = cur;

//cur = (value < cur->value) ? cur->left:cur->right;

if(value < cur->value) {

cur = cur->left;

} else {

cur = cur->right;

}

}

if(value < prev->value) {

prev->left = temp;

} else {

prev->right = temp;

}

}

// Level order traversal..

void levelOrderTraversal(mynode *root) {

mynode *queue[100] = {(mynode *)0}; // Important to initialize!

int size = 0;

int queue_pointer = 0;

while(root) {

printf("[%d] ", root->value);

if(root->left) {

queue[size++] = root->left;

}

if(root->right) {

queue[size++] = root->right;

}

root = queue[queue_pointer++];

}

}

// Kesavan

Answer 3

#include <stdio.h>

#include <conio.h>

#include <alloc.h>

#define TRUE 1

#define FALSE 0

#define MAX 8

struct node

{

int data ;

struct node *next ;

} ;

int visited[MAX] ;

int q[8] ;

int front, rear ;

void bfs ( int, struct node ** ) ;

struct node * getnode_write ( int ) ;

void addqueue ( int ) ;

int deletequeue( ) ;

int isempty( ) ;

void del ( struct node * ) ;

void main( )

{

struct node *arr[MAX] ;

struct node *v1, *v2, *v3, *v4 ;

int i ;

clrscr( ) ;

v1 = getnode_write ( 2 ) ;

arr[0] = v1 ;

v1 -> next = v2 = getnode_write ( 3 ) ;

v2 -> next = NULL ;

v1 = getnode_write ( 1 ) ;

arr[1] = v1 ;

v1 -> next = v2 = getnode_write ( 4 ) ;

v2 -> next = v3 = getnode_write ( 5 ) ;

v3 -> next = NULL ;

v1 = getnode_write ( 1 ) ;

arr[2] = v1 ;

v1 -> next = v2 = getnode_write ( 6 ) ;

v2 -> next = v3 = getnode_write ( 7 ) ;

v3 -> next = NULL ;

v1 = getnode_write ( 2 ) ;

arr[3] = v1 ;

v1 -> next = v2 = getnode_write ( 8 ) ;

v2 -> next = NULL ;

v1 = getnode_write ( 2 ) ;

arr[4] = v1 ;

v1 -> next = v2 = getnode_write ( 8 ) ;

v2 -> next = NULL ;

v1 = getnode_write ( 3 ) ;

arr[5] = v1 ;

v1 -> next = v2 = getnode_write ( 8 ) ;

v2 -> next = NULL ;

v1 = getnode_write ( 3 ) ;

arr[6] = v1 ;

v1 -> next = v2 = getnode_write ( 8 ) ;

v2 -> next = NULL ;

v1 = getnode_write ( 4 ) ;

arr[7] = v1 ;

v1 -> next = v2 = getnode_write ( 5 ) ;

v2 -> next = v3 = getnode_write ( 6 ) ;

v3 -> next = v4 = getnode_write ( 7 ) ;

v4 -> next = NULL ;

front = rear = -1 ;

bfs ( 1, arr ) ;

for ( i = 0 ; i < MAX ; i++ )

del ( arr[i] ) ;

getch( ) ;

}

void bfs ( int v, struct node **p )

{

struct node *u ;

visited[v - 1] = TRUE ;

printf ( "%d\t", v ) ;

addqueue ( v ) ;

while ( isempty( ) -1 )

return TRUE ;

return FALSE ;

}

void del ( struct node *n )

{

struct node *temp ;

while ( n != NULL )

{

temp = n -> next ;

free ( n ) ;

n = temp ;

}

}

Answer 4

Who's your teacher? There is supposed to be a general algorithm breadth first search. You can use that algorithm. Programming languages do not matter, its the algorithm that counts. You can use any language you like. Its just a matter of learning C.

Breadth first search algorithm:

http://renaud.waldura.com/portfolio/graph-algorithms/

Hope this helps. Who's your teacher? There is supposed to be a general algorithm breadth first search. You can use that algorithm. Programming languages do not matter, its the algorithm that counts. You can use any language you like. Its just a matter of learning C.

Breadth first search algorithm:

http://renaud.waldura.com/portfolio/graph-algorithms/

Hope this helps.

Answer 5

#include
#define MAX 20

typedef enum boolean{false,true} bool;
int adj[MAX][MAX];
bool visited[MAX];
int n; /* Denotes number of nodes in the graph */
main()
{
int i,v,choice;

create_graph();
while(1)
{
printf("\n");
printf("1. Adjacency matrix\n");
printf("2. Depth First Search using stack\n");
printf("3. Depth First Search through recursion\n");
printf("4. Breadth First Search\n");
printf("5. Adjacent vertices\n");
printf("6. Components\n");
printf("7. Exit\n");
printf("Enter your choice : ");
scanf("%d",&choice);

switch(choice)
{
case 1:
printf("Adjacency Matrix\n");
display();
break;
case 2:
printf("Enter starting node for Depth First Search : ");
scanf("%d",&v);
for(i=1;i<=n;i++)
visited[i]=false;
dfs(v);
break;
case 3:
printf("Enter starting node for Depth First Search : ");
scanf("%d",&v);
for(i=1;i<=n;i++)
visited[i]=false;
dfs_rec(v);
break;
case 4:
printf("Enter starting node for Breadth First Search : ");
scanf("%d", &v);
for(i=1;i<=n;i++)
visited[i]=false;
bfs(v);
break;
case 5:
printf("Enter node to find adjacent vertices : ");
scanf("%d", &v);
printf("Adjacent Vertices are : ");
adj_nodes(v);
break;
case 6:
components();
break;
case 7:
exit(1);
default:
printf("Wrong choice\n");
break;
}/*End of switch*/
}/*End of while*/
}/*End of main()*/

create_graph()
{
int i,max_edges,origin,destin;

printf("Enter number of nodes : ");
scanf("%d",&n);
max_edges=n*(n-1);

for(i=1;i<=max_edges;i++)
{
printf("Enter edge %d( 0 0 to quit ) : ",i);
scanf("%d %d",&origin,&destin);

if((origin==0) && (destin==0))
break;

if( origin > n destin > n origin<=0 destin<=0)
{
printf("Invalid edge!\n");
i--;
}
else
{
adj[origin][destin]=1;
}
}/*End of for*/
}/*End of create_graph()*/

display()
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%4d",adj[i][j]);
printf("\n");
}
}/*End of display()*/

dfs_rec(int v)
{
int i;
visited[v]=true;
printf("%d ",v);
for(i=1;i<=n;i++)
if(adj[v][i]==1 && visited[i]==false)
dfs_rec(i);
}/*End of dfs_rec()*/

dfs(int v)
{
int i,stack[MAX],top=-1,pop_v,j,t;
int ch;

top++;
stack[top]=v;
while (top>=0)
{
pop_v=stack[top];
top--; /*pop from stack*/
if( visited[pop_v]==false)
{
printf("%d ",pop_v);
visited[pop_v]=true;
}
else
continue;

for(i=n;i>=1;i--)
{
if( adj[pop_v][i]==1 && visited[i]==false)
{
top++; /* push all unvisited neighbours of pop_v */
stack[top]=i;
}/*End of if*/
}/*End of for*/
}/*End of while*/
}/*End of dfs()*/

bfs(int v)
{
int i,front,rear;
int que[20];
front=rear= -1;

printf("%d ",v);
visited[v]=true;
rear++;
front++;
que[rear]=v;

while(front<=rear)
{
v=que[front]; /* delete from queue */
front++;
for(i=1;i<=n;i++)
{
/* Check for adjacent unvisited nodes */
if( adj[v][i]==1 && visited[i]==false)
{
printf("%d ",i);
visited[i]=true;
rear++;
que[rear]=i;
}
}
}/*End of while*/
}/*End of bfs()*/

adj_nodes(int v)
{
int i;
for(i=1;i<=n;i++)
if(adj[v][i]==1)
printf("%d ",i);
printf("\n");
}/*End of adj_nodes()*/

components()
{
int i;
for(i=1;i<=n;i++)
visited[i]=false;
for(i=1;i<=n;i++)
{
if(visited[i]==false)
dfs_rec(i);
}
printf("\n");
}/*End of components()*/

Answer 6

Get the Complete Source Code to Implement DFS from

http://c-madeeasy.blogspot.com/2011/08/dfsdepth-first-search-program-in-java.html