C++ :: Breadth-first search algorithm (BFS)

Breadth-first search গ্রাফ অনুসন্ধানের জন্য একটি সহজ অ্যালগরিদম এবং অনেক গুরুত্বপূর্ণ গ্রাফ অ্যালগরিদমের জন্য এটি হচ্ছে মূল আদর্শ। Prim’s minimum-spanning tree অ্যালগরিদম এবং Dijkstra’s single-source shortest-paths অ্যালগরিদম Breadth-first search -এর আইডিয়াগুলি অনুসরন করে।

.:: PSEUDOCODE ::.

---

BFS(G,s)
    for each vertex u ∈ G.V - {s}
        u.color = WHITE
        u.d = ∞
        u.π = NIL
    s.color = GRAY
    s.d = 0
    s.π = NIL
    Q = ∅
    ENQUEUE(Q,s)
    while Q ≠ ∅
        u = DEQUEUE(Q)
        for each v ∈ G.Adj[u]
            if v.color == WHITE
                v.color = GRAY
                v.d = u.d + 1
                v.π = u
                ENQUEUE(Q,v)
        u.color = BLACK

.:: C++ Code ::.

---

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <limits>
#define MAX 101
using namespace std;

enum colors {BLACK, WHITE, GRAY};
int color[MAX], d[MAX], p[MAX], vertex, edge;
int INF = numeric_limits<int>::max();
int NIL = numeric_limits<int>::min();

void BFS(vector<int>[],int);
void PRINT_PATH(vector<int>[],int,int);

int main(void)
{
    //freopen("bfs.txt", "r", stdin);
    vector<int> adjList[MAX];
    int u, v;
    cin >> vertex >> edge;

    for(int e=1; e<=edge; e++) {
        cin >> u >> v;
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }

    BFS(adjList, 1);
    PRINT_PATH(adjList, 1, 4);

    return 0;
}

void BFS(vector<int> G[], int s) {
    for(int u=0; u<=vertex; u++) {
        color[u] = WHITE;
        d[u] = INF;
        p[u] = NIL;
    }

    color[s] = GRAY;
    d[s] = 0;
    p[s] = NIL;

    queue<int> Q; Q.push(s);

    while( !Q.empty()) {
        int u = Q.front(); Q.pop();
        for(int i=0; i<G[u].size(); i++) {
            if(color[G[u][i]] == WHITE) {
                color[G[u][i]] = GRAY;
                d[G[u][i]] = d[u] + 1;
                p[G[u][i]] = u;
                Q.push(G[u][i]);
            }
        }
        color[u] = BLACK;
    }
}

void PRINT_PATH(vector<int> G[], int s, int v) {
    if(v == s)
        cout << s;
    else if(p[v] == NIL)
        cout << "no path from " << s << " to " << v << " exists";
    else {
        PRINT_PATH(G, s, p[v]);
        cout << " -> ";
        cout << v;
    }
}

.:: Sample Input ::.

---

6 10
1 2
1 5
2 6
3 4
3 6
3 7
4 7
4 8
6 7
7 8

.:: Sample Output ::.

---

1 -> 2 -> 6 -> 3 -> 4

.:: BFS Related UVa Problems ::.

---

• 314 - Robot
• 417 - Word Index
• 439 - Knight Moves
• 532 - Dungeon Master
• 567 - Risk
• 10044 - Erdos numbers
• 10047 - The Monocycle
• 10067 - Playing with Wheels
• 10682 - Forro Party
• 10993 - Ignoring Digits
• 11352 - Crazy King

Refference: Introduction to Algorithms - Thomas H. Cormen