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

Đồ thị là cây nếu không chứa chu trình. Chương trình này kiểm tra đồ thị có hướng có phải cây hay không 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 và trong ngăn xếp đệ quy.
    b) Đệ quy cho các đỉnh kề.
    c) Gỡ nút khỏi ngăn xếp đệ quy.
  hàm cyclic():
    a) Đánh dấu tất cả chưa thăm và không trong ngăn xếp.
    b) Gọi cyclicUtil() để phát hiện chu trình.
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[], bool *rs);
public:
    G(int V);
    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);
}

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

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

int main() {
    G g(4);
    g.addEd(0, 2);
    g.addEd(1, 2);
    g.addEd(2, 0);
    g.addEd(3, 2);
    if (g.cyclic())
        cout << "Directed Graph isn't a tree";
    else
        cout << "Directed Graph is a tree";
    return 0;
}

Kết quả

Directed Graph isn't a tree