Блог пользователя Nourhan_Abo-Heba

Автор Nourhan_Abo-Heba, история, 9 месяцев назад, По-английски

BFS is one of the most important graph algorithms, especially when we want to find the shortest path in an unweighted graph.

Why BFS?

  • DFS is not suitable for shortest path problems because it may go deep into one branch until reaching a leaf, even if a shorter path exists.
  • BFS explores the graph level by level, which guarantees that the first time we reach a node, we reached it using the minimum number of edges.

How BFS works

  • We use a queue
  • Start from the source node
  • Visit all neighbors (level 1)
  • Then neighbors of neighbors (level 2), and so on

Queue order example:

X
x1  x2
x11 x12 x21 x22
x111 x112 x221 x222 ...

This level-by-level traversal is exactly why BFS gives the shortest path.


Key Idea for Shortest Path

  • Store (node, distance)
  • When we reach the destination node for the first time, that distance is the shortest path.

BFS Implementation

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
vector<int> adj[N];
bool vis[N];

int bfs(int start, int end) {
    queue<pair<int,int>> q;
    q.push({start, 0});
    vis[start] = true;

    while (!q.empty()) {
        auto [node, dist] = q.front();
        q.pop();

        if (node == end)
            return dist;

        for (int nxt : adj[node]) {
            if (!vis[nxt]) {
                vis[nxt] = true;
                q.push({nxt, dist + 1});
            }
        }
    }
    return -1; // no path
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    cout << bfs(1, 5);
}

Complexity

  • Time: O(n + m)
  • Space: O(n)

Final Notes (Blog Style Tips)

  • BFS = shortest path in unweighted graphs
  • DFS = exploring paths, not shortest
  • Always mark visited when pushing to queue
  • BFS is basically multi-source Dijkstra with weight = 1
  • Проголосовать: нравится
  • -19
  • Проголосовать: не нравится

»
9 месяцев назад, скрыть # |
 
Проголосовать: нравится -13 Проголосовать: не нравится

Auto comment: topic has been updated by Nourhan_Abo-Heba (previous revision, new revision, compare).

»
9 месяцев назад, скрыть # |
 
Проголосовать: нравится -10 Проголосовать: не нравится

One moment:

Better to use vector<int> dist(node_count, -1); This vector can store if node is visited, and the min_distance between some node to this one. And, if you use 1-indexded graph nodes then initialize:

vector<int> dist(node_count + 1, -1);

»
9 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Nourhan_Abo-Heba (previous revision, new revision, compare).