Kiểm tra đồ thị hai phần (Bipartite) bằng DFS trong C++

Đồ thị hai phần (bipartite graph) là đồ thị có thể tô màu bằng hai màu sao cho các đỉnh trong cùng một tập có cùng màu. Đây là chương trình C++ kiểm tra đồ thị có phải hai phần hay không bằng DFS.

Thuật toán

Bắt đầu
  Mảng color[] lưu 0 hoặc 1 cho mỗi nút biểu thị màu đối lập.
  Gọi hàm DFS từ một nút bất kỳ.
  Nếu nút w chưa được thăm, gán !color[v] cho color[w] và gọi DFS đệ quy
  để thăm các nút kề w.
  Nếu tại bất kỳ thời điểm nào color[u] bằng !color[v], thì đồ thị là hai phần.
  Sửa đổi hàm DFS.
Kết thúc

Ví dụ mã nguồn

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

void addEd(vector<int> adj[], int w, int v) { // thêm cạnh vào đồ thị
    adj[w].push_back(v); // thêm v vào danh sách w
    adj[v].push_back(w); // thêm w vào danh sách v
}

bool Bipartite(vector<int> adj[], int v, vector<bool>& visited, vector<int>& color) {
    for (int w : adj[v]) {
        // nếu đỉnh w chưa được khám phá
        if (visited[w] == false) {
            // đánh dấu đỉnh hiện tại đã thăm
            visited[w] = true;
            color[w] = !color[v]; // tô màu ngược lại cha
            if (!Bipartite(adj, w, visited, color))
                return false;
        }
        // nếu hai đỉnh kề cùng màu thì đồ thị không phải hai phần
        else if (color[w] == color[v])
            return false;
    }
    return true;
}

int main() {
    int M = 6;
    vector<int> adj[M + 1];
    // mảng kiểm tra nút đã khám phá hay chưa
    vector<bool> visited(M + 1);
    vector<int> color(M + 1); // tô màu đỉnh với 2 màu
    addEd(adj, 3, 2);
    addEd(adj, 1, 4);
    addEd(adj, 2, 1);
    addEd(adj, 5, 3);
    addEd(adj, 6, 2);
    addEd(adj, 3, 1);
    visited[1] = true;
    color[1] = 0;
    if (Bipartite(adj, 1, visited, color)) {
        cout << "Đồ thị là hai phần (Bipartite)";
    } else {
        cout << "Đồ thị KHÔNG phải hai phần (Bipartite)";
    }
    return 0;
}

Kết quả

Đồ thị KHÔNG phải hai phần (Bipartite)