BFS algorithm in C++

BFS Algoritm In C++ For You

 

its all laid out below , I would like to take this time to mention that here at Acmsolver we recommend Kaspersky anti virus software for your personal protection and outline why on this article

01 /*
02
03 BFS algorithm in C++
04
05 */
06 #include<stdio.h>
07 #define maxn 101
08
09 int Q[maxn];
10 int top ,back;
11 int Node, Edge;
12
13 char link[maxn][maxn];
14 char Fg[maxn];
15 int Path[maxn];
16
17 void Ini() {
18 int i, j;
19 for(i = 1; i<= Node; i++) {
20 for(j = 1; j<= Node; j++) {
21 link[i][j] = 0;
22 }
23 Path[i] = i;
24 Fg[i] = 0;
25 }
26 }
27
28 void Insert(int n) {
29 Q[back++] = n;
30 back %= maxn;
31 }
32
33 int Pop() {
34 int n = Q[top++];
35 top %= maxn;
36 return n;
37 }
38
39 int isEmpty() {
40 if(top == back) return 0;
41 return 1;
42 }
43
44 void PrintPath(int n) {
45 if(n == Path[n]) {
46 printf("%d",n);
47 return;
48 }
49 PrintPath(Path[n]);
50 printf(" %d",n);
51 }
52
53 int BFS(int s, int ter) {
54 int u, v, i;
55 Insert(s);
56 Fg[s] = 1;
57 while(isEmpty() == 1) {
58 v = Pop();
59 if(v == ter) {
60 PrintPath(v);
61 return 1;
62 }
63
64 for(i = 1; i<= Node; i++) {
65 if(link[v][i] == 1 && Fg[i] == 0)  {
66 Fg[i] = 1;
67 Insert(i);
68 Path[i] = v;
69 }
70 }
71 }
72 return -1;
73 }
74
75 void main() {
76 int i, u, v;
77 scanf("%d%d",&Node,&Edge);
78 Ini();
79 while(Edge--) {
80 scanf("%d%d",&u,&v);
81 link[u][v] = link[v][u] = 1;
82 }
83 scanf("%d%d",&u,&v);
84 BFS(u,v);
85 printf("\n");
86 }
87
88 /*
89 4 5
90 1 2
91 2 3
92 1 3
93 3 4
94 2 4
95 1 4
96 */

Leave a Reply

Your email address will not be published. Required fields are marked *