Breadth First Search & Depth First Search Implementation in C/C++

<syntaxhighlight lang="C" name = "bfs_dfs">

1. include<iostream>

using namespace std;

struct vert { char neighbour[20]; int nn; char name; int color; int d; char pi; };

void bfs(char start); void dfs(char start); int vi = 0; vert vertex[20];

int findi(char a) { int i; for(i = 0; i < vi; i++) if(vertex[i].name == a) return i; return 0; }

int main() { char b, a,start; int c, d, i, u;

cout << "Enter the edges\n0 to stop:\n "; while(1) { cin >> a; if(a == '0') break; cin >> b; c = 0,d = 0; for(i = 0 ; i < vi; i++) { if(a == vertex[i].name) { vertex[i].neighbour[vertex[i].nn++] = b; c++; } if(b == vertex[i].name) { vertex[i].neighbour[vertex[i].nn++] = a; d++; } } if(c == 0) { vertex[vi].name = a; vertex[vi].nn = 0; vertex[vi++].neighbour[vertex[vi].nn++] = b; } if(d == 0) { vertex[vi].name = b; vertex[vi].nn = 0; vertex[vi++].neighbour[vertex[vi].nn++] = a; } } cout << "Enter the starting vertex: "; cin >> start; bfs(start); cout << endl; dfs(start); }

void bfs(char start) { int i; int front = 0, back = 0, u; int queue[50]; for(i = 0; i < vi; i++) { if(vertex[i].name == start) { vertex[i].color = 1; vertex[i].d = 0; vertex[i].pi = 0; queue[back++] = i; } else { vertex[i].color = 0; vertex[i].d = -1; vertex[i].pi = 0; } } while(front < back) { u = queue[front++]; cout << vertex[u].name <<"\t"; for(i = 0; i<vertex[u].nn; i++) { if(vertex[findi(vertex[u].neighbour[i])].color == 0) { vertex[findi(vertex[u].neighbour[i])].color = 1; vertex[findi(vertex[u].neighbour[i])].d = vertex[u].d+1; vertex[findi(vertex[u].neighbour[i])].pi = vertex[u].pi; queue[back++] = findi(vertex[u].neighbour[i]); } } vertex[u].color = 2; } }

void dfs(char start) { int i; int top = 0,u; int stack[50]; for(i = 0;i < vi; i++) { if(vertex[i].name == start) { vertex[i].color = 1; vertex[i].d = 0; vertex[i].pi = 0; stack[top++] = i; } else { vertex[i].color = 0; vertex[i].d = -1; vertex[i].pi = 0; } } while(top > 0) { u = stack[--top]; cout << vertex[u].name << "\t"; for(i = 0;i < vertex[u].nn; i++) { if(vertex[findi(vertex[u].neighbour[i])].color == 0) { vertex[findi(vertex[u].neighbour[i])].color = 1; vertex[findi(vertex[u].neighbour[i])].d = vertex[u].d+1; vertex[findi(vertex[u].neighbour[i])].pi = vertex[u].pi; stack[top++] = findi(vertex[u].neighbour[i]); } } vertex[u].color = 2; } }

</syntaxhighlight>

Tweet