检查给定的树形图在 C++ 中是否线性
在此处,我们将了解如何检查树形图是否线性。线性树形图可以用一行表示,这是一个线性树形图的示例。
但这不是线性的 −
若要检查图形是否线性,我们可以遵循两个条件
- 如果节点数为 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
广告