โปรแกรม C++ ตรวจสอบกราฟมีทิศทางเป็นต้นไม้ (Tree) ด้วย DFS

บทนำ

กราฟจะเป็นต้นไม้ (Tree) ถ้าไม่มีวงจร (Cycle) นี่คือโปรแกรม C++ ตรวจสอบว่ากราฟมีทิศทางเป็นต้นไม้หรือไม่โดยใช้ DFS

อัลกอริทึม

Begin function cyclicUtil():
  a) ทำเครื่องหมายโหนดปัจจุบันว่าเยี่ยมชมแล้วและอยู่ใน recursion stack
  b) เรียกซ้ำสำหรับทุกโหนดที่ติดกับโหนดนี้
  c) นำโหนดออกจาก recursion stack

function cyclic():
  a) ทำเครื่องหมายทุกโหนดว่าไม่ได้เยี่ยมชมและไม่อยู่ใน recursion stack
  b) เรียกฟังก์ชัน CyclicUtil() เพื่อตรวจจับวงจรในต้นไม้ต่างๆ
End

ตัวอย่างโค้ด C++

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

class Graph {
    int V;
    list<int> *adj;
    bool CyclicUtil(int v, bool visited[], bool *recurS);
public:
    Graph(int V);
    void addEdge(int v, int w);
    bool cyclic();
};

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

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

bool Graph::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 Graph::cyclic() {
    bool *visited = new bool[V];
    bool *recurS = new bool[V];
    for (int i = 0; i < V; i++) {
        visited[i] = false;
        recurS[i] = false;
    }
    for (int i = 0; i < V; i++)
        if (CyclicUtil(i, visited, recurS))
            return true;
    return false;
}

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

ผลลัพธ์

Directed Graph isn't a tree