ตรวจสอบว่า Tree Graph เป็นแบบเส้นตรงหรือไม่ใน C++

ในบทความนี้เราจะมาดูวิธีการตรวจสอบว่า Tree Graph ที่กำหนดเป็นแบบเส้นตรง (Linear) หรือไม่ Tree Graph แบบเส้นตรงคือโครงสร้างที่สามารถแสดงผลในบรรทัดเดียวได้ ตัวอย่างเช่นภาพด้านล่างนี้เป็น Linear Tree Graph

แต่ภาพนี้ไม่ใช่ Linear Tree Graph

ในการตรวจสอบว่า Graph เป็นแบบเส้นตรงหรือไม่ เราสามารถใช้เงื่อนไข 2 ข้อต่อไปนี้:

• ถ้าจำนวนโหนด (Nodes) เท่ากับ 1 แล้ว Tree Graph นั้นเป็นแบบเส้นตรง
• ถ้า (n - 2) โหนดมี in-degree เท่ากับ 2

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

#include <iostream>
#include <vector>
#define N 4
using namespace std;

class Graph {
private:
    int V;
    vector<int> *adj;
public:
    Graph(int v) {
        V = v;
        adj = new vector<int>[v];
    }
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    bool isLinear() {
        if (V == 1)
            return true;
        int count = 0;
        for (int i = 0; i < V; i++) {
            if (adj[i].size() == 2)
                count++;
        }
        if (count == V - 2)
            return true;
        else
            return false;
    }
};

int main() {
    Graph g1(3);
    g1.addEdge(0, 1);
    g1.addEdge(0, 2);
    if (g1.isLinear())
        cout << "The graph is linear";
    else
        cout << "The graph is not linear";
}

ผลลัพธ์

The graph is linear