นับจำนวนต้นไม้ในป่า (Forest) ด้วย DFS ใน C++

โจทย์: ให้กราฟแบบไม่มีทิศทาง (Forest = ชุดของต้นไม้) ต้องการนับจำนวน Connected Component (ต้นไม้) โดยใช้ DFS

แนวคิด

แต่ละ Connected Component คือต้นไม้หนึ่งต้น ทำ DFS จากโหนดที่ยังไม่ได้เยี่ยมชม แต่ละครั้งที่เริ่ม DFS ใหม่ = พบต้นไม้ใหม่

โค้ด C++

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

void insert(vector<int> vec[], int parent, int child) {
    vec[parent].push_back(child);
    vec[child].push_back(parent);
}

void dfs(int u, vector<int> vec[], vector<bool>& visited) {
    visited[u] = true;
    for (int v : vec[u]) {
        if (!visited[v])
            dfs(v, vec, visited);
    }
}

int Trees_Forest(vector<int> vec[], int vertices) {
    int count = 0;
    vector<bool> visited(vertices, false);
    for (int i = 0; i < vertices; i++) {
        if (!visited[i]) {
            dfs(i, vec, visited);
            count++;
        }
    }
    return count;
}

int main() {
    int vertices = 9;  // 0-8
    vector<int> vec[vertices];
    
    insert(vec, 1, 3);
    insert(vec, 2, 8);
    insert(vec, 2, 6);
    insert(vec, 3, 5);
    insert(vec, 3, 7);
    insert(vec, 4, 8);
    
    cout << "Count of number of trees in a forest are: "
         << Trees_Forest(vec, vertices);
    return 0;
}

ผลลัพธ์

Count of number of trees in a forest are: 3

การวิเคราะห์ตัวอย่าง

Edges: {1,3}, {2,8}, {2,6}, {3,5}, {3,7}, {4,8}

Connected Components:

1. 0: โหนดเดี่ยว (isolated)
2. 1-3-5, 1-3-7: ต้นไม้ที่ 1 (โหนด 1,3,5,7)
3. 2-8-4, 2-6: ต้นไม้ที่ 2 (โหนด 2,4,6,8)

รวม 3 ต้นไม้ (รวมโหนด 0 ที่เดี่ยว)

ความซับซ้อน: Time O(V+E), Space O(V)