Chương trình C++ kiểm tra đồ thị hai phía bằng DFS

Đồ thị hai phía (bipartite) 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ía hay không sử dụng DFS.

Thuật toán

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

Ví dụ

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

void addEd(vector<int> adj[], int w, int v) // thêm cạnh
{
    adj[w].push_back(v);
    adj[v].push_back(w);
}

bool Bipartite(vector<int> adj[], int v, vector<bool>& visited, vector<int>& color) {
    for (int w : adj[v]) {
        if (visited[w] == false) {
            visited[w] = true;
            color[w] = !color[v]; // màu ngược lại cha
            if (!Bipartite(adj, w, visited, color))
                return false;
        }
        else if (color[w] == color[v]) // cùng màu -> không hai phía
            return false;
    }
    return true;
}

int main() {
    int M = 6;
    vector<int> adj[M + 1];
    vector<bool> visited(M + 1);
    vector<int> color(M + 1);
    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 << "Graph is Bipartite";
    else
        cout << "Graph is not Bipartite";
    return 0;
}

Kết quả

Graph is not Bipartite