Kiểm tra đồ thị cây có phải tuyến tính hay không trong C++

Chúng ta sẽ xem cách kiểm tra xem một đồ thị cây có phải là tuyến tính hay không. Một đồ thị cây tuyến tính có thể được biểu diễn trên một đường thẳng, ví dụ như hình dưới đây là một đồ thị cây tuyến tính.

Nhưng hình dưới đây không phải là tuyến tính:

Để kiểm tra xem một đồ thị có tuyến tính hay không, ta có thể dựa trên hai điều kiện:

• Nếu số nút là 1, thì đồ thị cây là tuyến tính.
• Nếu (n – 2) nút có bậc vào (in-degree) bằng 2.

Ví dụ

#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";
}

Kết quả

The graph is linear