-
Notifications
You must be signed in to change notification settings - Fork 0
/
bfs.c
112 lines (89 loc) · 1.72 KB
/
bfs.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<stdio.h>
# include <stdlib.h>
//# include <conio.h>
int q[ 20 ], front = -1, rear = -1, vis[ 20 ];
int a[20][20];
int delete();
void add ( int item );
void bfs( int s, int n );
void main()
{
int n, i, s,j;
// clrscr();
printf( "ENTER THE NUMBER VERTICES " );
scanf( "%d", &n );
for ( i = 1;i <= n;i++ )
{
for ( j = 1;j <= n;j++ )
{
printf( "ENTER 1 IF %d HAS A NODE WITH %d ELSE 0 ", i, j );
scanf( "%d", &a[ i ][ j ] );
}
}
printf( "THE ADJACENCY MATRIX IS\n" );
for ( i = 1;i <= n;i++ )
{
for ( j = 1;j <= n;j++ )
{
printf( " %d", a[ i ][ j ] );
}
printf( "\n" );
}
for ( i = 1;i <= n;i++ )
vis[ i ] = 0;
printf( "ENTER THE SOURCE VERTEX :" );
scanf( "%d", &s );
// bfs (source_node, total_nodes)
bfs( s, n );
// getch();
}
void bfs( int s, int n )
{
int p, i;
add( s );
vis[ s ] = 1;
p = delete();
if ( p != 0 )
printf( " %d", p );
while ( p != 0 )
{
for ( i = 1;i <= n;i++ )
if ( ( a[ p ][ i ] != 0 ) && ( vis[ i ] == 0 ) )
{
add( i );
vis[ i ] = 1;
}
p = delete();
if ( p != 0 )
printf( " %d ", p );
}
for ( i = 1;i <= n;i++ )
if ( vis[ i ] == 0 )
bfs( i, n );
}
void add( int item )
{
if ( rear == 19 )
printf( "QUEUE FULL" );
else
{
if ( rear == -1 )
{
q[ ++rear ] = item;
front++;
}
else
q[ ++rear ] = item;
}
}
int delete()
{
int k;
if ( ( front > rear ) || ( front == -1 ) )
return ( 0 );
else
{
k = q[ front++ ];
return ( k );
}
}