ICPC Competitive Programming
← กลับหน้าหลัก

Graph Traversal

BFS และ DFS สำหรับการท่องกราฟ

Graph Traversal

การท่องกราฟ (Graph Traversal) คือการเยี่ยมชม vertices ทั้งหมดในกราฟ มีสองวิธีหลักคือ BFS และ DFS

Breadth-First Search (BFS)

เยี่ยมชม vertices ตามลำดับ “ระดับความลึก” ใช้ Queue

Algorithm

  1. เริ่มจาก vertex ต้นทาง ใส่ลงใน queue
  2. ดึง vertex ออกจาก queue
  3. เยี่ยมชม neighbors ที่ยังไม่ได้เยี่ยม ใส่ลงใน queue
  4. ทำซ้ำจนกว่า queue จะว่าง

Implementation

void bfs(int start) {
    vector<bool> visited(n + 1, false);
    queue<int> q;
    
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        cout << u << " "; // Process vertex
        
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

BFS สำหรับหา Shortest Path (Unweighted)

vector<int> bfsShortestPath(int start) {
    vector<int> dist(n + 1, -1);
    queue<int> q;
    
    q.push(start);
    dist[start] = 0;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    
    return dist;
}

BFS สำหรับหา Path

vector<int> bfsPath(int start, int end) {
    vector<int> parent(n + 1, -1);
    queue<int> q;
    
    q.push(start);
    parent[start] = start;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        if (u == end) break;
        
        for (int v : adj[u]) {
            if (parent[v] == -1) {
                parent[v] = u;
                q.push(v);
            }
        }
    }
    
    // Reconstruct path
    if (parent[end] == -1) return {}; // ไม่มี path
    
    vector<int> path;
    for (int v = end; v != start; v = parent[v]) {
        path.push_back(v);
    }
    path.push_back(start);
    reverse(path.begin(), path.end());
    
    return path;
}

Complexity

  • Time: O(V+E)O(V + E)
  • Space: O(V)O(V)

Depth-First Search (DFS)

เยี่ยมชม vertices โดย “ลงลึก” ให้มากที่สุดก่อน แล้วค่อย backtrack

DFS แบบ Recursive

vector<bool> visited;

void dfs(int u) {
    visited[u] = true;
    cout << u << " "; // Process vertex
    
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

// เรียกใช้
visited.assign(n + 1, false);
dfs(1);

DFS แบบ Iterative (ใช้ Stack)

void dfsIterative(int start) {
    vector<bool> visited(n + 1, false);
    stack<int> st;
    
    st.push(start);
    
    while (!st.empty()) {
        int u = st.top();
        st.pop();
        
        if (visited[u]) continue;
        visited[u] = true;
        
        cout << u << " "; // Process vertex
        
        // Push in reverse order to maintain left-to-right order
        for (int i = adj[u].size() - 1; i >= 0; i--) {
            int v = adj[u][i];
            if (!visited[v]) {
                st.push(v);
            }
        }
    }
}

DFS Applications

1. ตรวจสอบ Cycle

// Undirected Graph
bool hasCycleUndirected(int u, int parent) {
    visited[u] = true;
    
    for (int v : adj[u]) {
        if (!visited[v]) {
            if (hasCycleUndirected(v, u)) return true;
        } else if (v != parent) {
            return true; // Back edge found
        }
    }
    return false;
}

// Directed Graph
vector<int> color; // 0: white, 1: gray, 2: black

bool hasCycleDirected(int u) {
    color[u] = 1; // gray
    
    for (int v : adj[u]) {
        if (color[v] == 1) return true; // Back edge
        if (color[v] == 0 && hasCycleDirected(v)) return true;
    }
    
    color[u] = 2; // black
    return false;
}

2. Topological Sort

vector<int> order;
vector<bool> visited;

void dfsTopSort(int u) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfsTopSort(v);
        }
    }
    order.push_back(u);
}

vector<int> topologicalSort() {
    visited.assign(n + 1, false);
    order.clear();
    
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfsTopSort(i);
        }
    }
    
    reverse(order.begin(), order.end());
    return order;
}

3. นับ Connected Components

int countComponents() {
    visited.assign(n + 1, false);
    int count = 0;
    
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfs(i);
            count++;
        }
    }
    
    return count;
}

4. หา Bridge (เส้นเชื่อมสำคัญ)

vector<int> disc, low;
vector<pair<int, int>> bridges;
int timer = 0;

void dfsBridge(int u, int parent) {
    disc[u] = low[u] = timer++;
    
    for (int v : adj[u]) {
        if (disc[v] == -1) { // ยังไม่เคยเยี่ยม
            dfsBridge(v, u);
            low[u] = min(low[u], low[v]);
            
            if (low[v] > disc[u]) {
                bridges.push_back({u, v});
            }
        } else if (v != parent) {
            low[u] = min(low[u], disc[v]);
        }
    }
}

void findBridges() {
    disc.assign(n + 1, -1);
    low.assign(n + 1, -1);
    
    for (int i = 1; i <= n; i++) {
        if (disc[i] == -1) {
            dfsBridge(i, -1);
        }
    }
}

Complexity

  • Time: O(V+E)O(V + E)
  • Space: O(V)O(V) (Stack space for recursion)

BFS vs DFS

คุณสมบัติBFSDFS
Data StructureQueueStack/Recursion
MemoryO(V)O(V) หรือมากกว่าO(h)O(h) where h = depth
Shortest Pathใช่ (unweighted)ไม่
Cycle Detectionได้ได้
Topological Sortได้ (Kahn’s)ได้
Connected Componentsได้ได้

0-1 BFS

สำหรับ graph ที่มี edge weight เป็น 0 หรือ 1 ใช้ deque แทน priority queue

vector<int> bfs01(int start) {
    vector<int> dist(n + 1, INF);
    deque<int> dq;
    
    dist[start] = 0;
    dq.push_front(start);
    
    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();
        
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                
                if (w == 0) {
                    dq.push_front(v);
                } else {
                    dq.push_back(v);
                }
            }
        }
    }
    
    return dist;
}

Complexity: O(V+E)O(V + E)

Multi-Source BFS

BFS จากหลาย source พร้อมกัน

vector<int> multiSourceBFS(vector<int>& sources) {
    vector<int> dist(n + 1, INF);
    queue<int> q;
    
    for (int s : sources) {
        dist[s] = 0;
        q.push(s);
    }
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int v : adj[u]) {
            if (dist[v] == INF) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    
    return dist;
}

ตัวอย่างโจทย์

โจทย์: Grid BFS (Maze)

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int bfsMaze(vector<string>& grid, int sr, int sc, int er, int ec) {
    int rows = grid.size(), cols = grid[0].size();
    vector<vector<int>> dist(rows, vector<int>(cols, -1));
    queue<pair<int, int>> q;
    
    q.push({sr, sc});
    dist[sr][sc] = 0;
    
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        
        if (x == er && y == ec) return dist[x][y];
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols 
                && grid[nx][ny] != '#' && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    
    return -1; // ไม่มีทาง
}

สรุป

Algorithmใช้สำหรับ
BFSShortest path (unweighted), Level-order
DFSCycle detection, Topological sort, Connected components
0-1 BFSShortest path (0-1 weights)
Multi-Source BFSDistance from multiple sources

💡 Tip: ถ้าต้องการ shortest path ใน unweighted graph ให้ใช้ BFS เสมอ