Chương trình C++ kiểm tra đồ thị vô hướng có phải cây không bằng DFS

Đồ thị vô hướng là cây nếu không có chu trình. Chương trình này kiểm tra bằng DFS.

Thuật toán

Bắt đầu
  hàm cyclicUtil():
    A) Đánh dấu nút hiện tại đã thăm.
    B) Đệ quy cho các đỉnh kề.
    C) Nếu kề chưa thăm -> đệ quy.
    D) Nếu kề đã thăm và không phải cha -> có chu trình.
  hàm cyclic():
    A) Đánh dấu tất cả chưa thăm.
    B) Gọi cyclicUtil() cho từng thành phần liên thông.
Kết thúc

Ví dụ

#include <iostream>
#include <list>
#include <limits.h>
using namespace std;

class G {
    int n;
    list<int> *adj;
    bool CyclicUtil(int v, bool visited[], int par);
public:
    G(int n);
    void addEd(int v, int w);
    bool cyclic();
};

G::G(int n) {
    this->n = n;
    adj = new list<int>[n];
}

void G::addEd(int v, int u) {
    adj[v].push_back(u);
    adj[u].push_back(v);
}

bool G::CyclicUtil(int v, bool visited[], int par) {
    visited[v] = true;
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i) {
        if (!visited[*i]) {
            if (CyclicUtil(*i, visited, v))
                return true;
        }
        else if (*i != par)
            return true;
    }
    return false;
}

bool G::cyclic() {
    bool *visited = new bool[n];
    for (int i = 0; i < n; i++)
        visited[i] = false;
    for (int u = 0; u < n; u++)
        if (!visited[u])
            if (CyclicUtil(u, visited, -1))
                return true;
    return false;
}

int main() {
    G g1(4);
    g1.addEd(0, 1);
    g1.addEd(1, 2);
    g1.cyclic() ? cout << "Undirected Graph isn't a tree\n" : cout << "Undirected Graph is a tree\n";
    return 0;
}

Kết quả

Undirected Graph is a tree