Program that implements breadth first search algorithm?

Answer 1

#include <stdio.h>

#include <conio.h>

#include <malloc.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 * ) ;

int main( )

{

struct node *arr[MAX] ;

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

int i ;

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( ) ;

return 0;

}

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 2

1. #include
2. #define MAX5
3. int dfs(int adj[][MAX], int visited[], int start)
4. {
5. int stack[MAX];
6. int top=-1,i;
7. printf("%c-",start+65);
8. visited[start]=1;
9. stack[++top]=start;
10. while(top!=-1)
11. {
12. start=stack[top];
13. for(i=0;i
14. {
15. if(adj[start][i]&&visited[i]==0)
16. {
17. stack[++top]=i;
18. printf('%c-",i+65);
19. visited[i]=1;
20. break;
21. }
22. }
23. if(i==MAX)
24. top--;
25. }
26. return 0;
27. }
28. int main()
29. {
30. int adj[MAX][MAX]={{0,0,1,1,0},{0,0,0,0,0},{0,1,0,1,1},{0,0,0,0,1},{0,0,0,1,0}};
31. int visited[MAX]={0};
32. printf("DFS Traversal : ");
33. dfs(adj,visited,0);
34. printf("\n");
35. return 0;
36. }

By Malek Alatomi