-
Notifications
You must be signed in to change notification settings - Fork 1
/
bfs.cpp
54 lines (44 loc) · 1.01 KB
/
bfs.cpp
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
#include<iostream>
using namespace std;
int q[50], front = 0, rear = -1;
void insert_q(int ele)
{
q[++rear] = ele;
}
int delete_q()
{
if(front > rear)
return -1;
return q[front++];
}
//Representation of the graph
int G[4][4]={ {0, 1, 0, 1},
{1, 0, 1, 0},
{0, 1, 0, 0},
{1, 0, 0, 0} };
//Mark all nodes as unvisited
int visited[4] = {0,0,0,0};
void bfs(int v)
{
//Mark current node as visited and display
visited[v] = 1;
cout<<v<<" ";
//For each node
for(int i = 0; i < 4; ++i)
//Check if it is connected to current node and unvisited
if( (G[v][i] == 1) && (visited[i] != 1) )
{
//Mark as visited and add to queue
visited[i] = 1;
insert_q(i);
}
int u;
//BFS on each node in the queue
while((u = delete_q()) != -1)
bfs(u);
}
int main()
{
bfs(0); //Starting node to perform BFS
return 0;
}