เราจะมาดูวิธีการตรวจสอบว่ากราฟต้นไม้เป็นเส้นตรงหรือไม่ กราฟต้นไม้เชิงเส้นสามารถแสดงเป็นเส้นเดียว สมมติว่านี่คือตัวอย่างของกราฟต้นไม้เชิงเส้น
แต่นี่ไม่ใช่เชิงเส้น −
การตรวจสอบกราฟเป็นเส้นตรงหรือไม่ ทำได้ 2 เงื่อนไข
- ถ้าจำนวนโหนดเป็น 1 กราฟต้นไม้จะเป็นเส้นตรง
- ถ้า (n – 2) ของโหนดมีระดับ 2
ตัวอย่าง
#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
