No: 11
1. vision:
2. OBJECTIVE: Program
to implement Depth
first search in c programming.
3. THEORY:
Depth-first
search (DFS) is an algorithm for
traversing or searching tree or graph data
structures. One starts at the root (selecting some
arbitrary node as the root in the case of a graph) and explores as far as
possible along each branch before backtracking. DFS is
typically used to traverse an entire graph, For applications of DFS in relation
to specific domains, such as searching for solutions in artificial
intelligence or
web-crawling, the graph to be traversed is often either too large to visit in
its entirety or infinite.
1. PROGRAM:
#include<stdio.h>
void DFS(int);
int
G[10][10],visited[10],n; //n is no of
vertices and graph is sorted in array G[10][10]
void main()
{
int i,j;
printf("Enter number of
vertices:");
scanf("%d",&n);
//read the adjecency matrix
printf("\nEnter adjecency matrix of
the graph:");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);
//visited is initialized to zero
for(i=0;i<n;i++)
visited[i]=0;
DFS(0);
}
void DFS(int i)
{
int j;
printf("\n%d",i);
visited[i]=1;
for(j=0;j<n;j++)
if(!visited[j]&&G[i][j]==1)
DFS(j);
}
5. OUTPUT:
------------------------------------------
------------------------------------------
6. conclusion:
Thus we studied Depth first
search program and executed successfully.
7. Discussion Questions:
1) what is Depth
first search?
_________________________________________________________________________________________________________________________________________________________
2)
What is
difference between BFS and DFS?
______________________________________________________________________________________________________________________________________________________
3) What is the complexity of DFS?
______________________________________________________________________________________________________________________________________________________
No comments:
Post a Comment