数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化学
生物
数学
英语
经济
心理
社会学
时尚学
法律学检查给定的树形图在 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
更新日期：22-Oct-2019
145 次浏览
广告