C++有向无环图DAG类的构建
时间: 2023-10-23 08:16:36 浏览: 49
以下是一个简单的 C++ 实现,用于构建有向无环图(DAG)的类:
```c++
#include <vector>
#include <queue>
using namespace std;
class DAG {
private:
int V; // 顶点数
vector<int> *adj; // 邻接表
public:
DAG(int V) {
this->V = V;
adj = new vector<int>[V];
}
~DAG() {
delete[] adj;
}
void addEdge(int u, int v) {
adj[u].push_back(v);
}
vector<int> topologicalSort() {
vector<int> inDegree(V, 0); // 记录每个顶点的入度
vector<int> result; // 存储拓扑排序的结果
// 计算每个顶点的入度
for (int u = 0; u < V; u++) {
for (int v : adj[u]) {
inDegree[v]++;
}
}
// 将入度为 0 的顶点加入队列
queue<int> q;
for (int u = 0; u < V; u++) {
if (inDegree[u] == 0) {
q.push(u);
}
}
// 依次删除入度为 0 的顶点,并更新其邻接点的入度
while (!q.empty()) {
int u = q.front();
q.pop();
result.push_back(u);
for (int v : adj[u]) {
inDegree[v]--;
if (inDegree[v] == 0) {
q.push(v);
}
}
}
return result;
}
};
```
这个 DAG 类的构造函数需要传入一个整数 V,表示图中的顶点数。addEdge() 方法用于添加一条从顶点 u 到顶点 v 的有向边。topologicalSort() 方法返回一个 vector,表示该 DAG 的一个拓扑排序结果。
在使用该类时,首先要创建一个 DAG 对象,然后调用 addEdge() 方法添加所有的边。最后,调用 topologicalSort() 方法即可得到拓扑排序结果。例如:
```c++
int main() {
DAG g(6);
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(3, 4);
g.addEdge(3, 5);
vector<int> result = g.topologicalSort();
for (int u : result) {
cout << u << " ";
}
cout << endl;
return 0;
}
```
上面的例子中,我们创建了一个包含 6 个顶点的 DAG,并添加了 6 条边。最后,我们输出了该 DAG 的一个拓扑排序结果。