Kiểm tra xem một biểu đồ cây đã cho có tuyến tính hay không trong C ++

Ở đây chúng ta sẽ xem cách kiểm tra một biểu đồ dạng cây có tuyến tính hay không. Biểu đồ hình cây tuyến tính có thể được biểu thị bằng một dòng, giả sử đây là một ví dụ về biểu đồ hình cây tuyến tính.

Nhưng điều này không tuyến tính -

Để kiểm tra biểu đồ có tuyến tính hay không, chúng ta có thể tuân theo hai điều kiện

• Nếu số nút là 1, thì biểu đồ cây là tuyến tính
• Nếu (n - 2) các nút của nó có bậc 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";
}

Đầu ra

The graph is linear