Scribd
Upload
9 views

Programming On Graph

Algo on graph

Uploaded by

Ronit Deb
Copyright
© © All Rights Reserved
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
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