Scribd
Upload
9 views

Programming On Graph

Algo on graph

Uploaded by

Ronit Deb
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views

Programming On Graph

Algo on graph

Uploaded by

Ronit Deb
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Write a program to implement the breadth-first search algorithm.

#include <stdio .h>


#define MAX 10
void breadth_first_search(int adj(][MAX],int visited[],int start)
{
int queue(MAX],rear = -1,front =- 1, i;
queue[++rear] = start;
visited[start] = 1;
while(rear I= front)
{
start= queue[++front];
if(start == 4)
printf("S\t");
else
printf("%c \t",start + 65);
for(i = O; i < MAX; i++)
{
if(adj[start][i] == 1 && visited[i] O)
{
queue[++rear] = i;
visited(i] = 1;
}
}
}
}
int main()

{
int visited[MAX) = {O};
int adj[MAX)(MAX), i, j;
printf("\n Enter the adjacency matrix: ");
for(i = o; i < MAX; i++)
for(j = o; j < MAX; j++)
scanf("%d'", &adj[i)[j]);
breadth_first_search(adj,visited,O);
return O;
}
Output
Enter the adjacency matrix:
0 1 0 1 0
1 0 1 1 0
0 1 0 0 1
1 1 0 0 1
0 0 1 1 0
A B DC E
Write a program to implement the depth-first search algorithm.
#include <stdio.h>
#define MAX 5
void depth_first_search(int adj[][MAX],int visited[],int start)
{
int stack[MAX];
int top= -1, i;
printf("%c-",start + 65);
visited[start] = l;
stack[++top] = start;
while(top I = -1)
{
start= stack[top];
for(i = O; i < MAX; i++)
{
if(adj[start][i] && visited[i] = 0)
{
stack[++top] = i;
printf("%c-", i + 65);
visited[i] = l;
break;
}
}
if(i == MAX)
top--;
}
}
int main()
{
int adj[MAX)[MAX];
int visited[MAX) = {O}, i, j;

printf("\n Enter the adjacency matrix: ");


for(i = o; i < MAX; i++)
for(j = O; j < MAX; j++)
scanf( "%d"', &adj [ i)[j]);
printf("DFS Traversal: ");
depth_first_search(adj,visited,O) ;
printf("\n");
return o;
}
Output
Enter the adjacency matrix:
0 1 0 1 0
1 0 1 1 0
0 1 0 0 1
1 1 0 0 1
0 0 1 1 0
DFS Traversal: A - > C - > E ->

You might also like