对于给定的有向无环图,如何计算出度,给出它的c++代码
时间: 2024-09-07 12:03:36 浏览: 45
在有向无环图(DAG)中,度通常指的是一个顶点的入度(In-degree)和出度(Out-degree)。入度是指有多少条边的终点指向该顶点,而出度是指有多少条边从该顶点出发指向其他顶点。在C++中计算一个有向无环图的顶点的入度和出度,可以通过遍历图的邻接表来实现。
以下是一个简单的C++代码示例,用于计算并输出每个顶点的入度和出度:
```cpp
#include <iostream>
#include <vector>
// 函数用于计算并输出每个顶点的入度和出度
void computeDegrees(const std::vector<std::vector<int>>& adjList) {
int numVertices = adjList.size();
std::vector<int> inDegree(numVertices, 0); // 存储每个顶点的入度
std::vector<int> outDegree(numVertices, 0); // 存储每个顶点的出度
// 遍历所有顶点,计算出度
for (int i = 0; i < numVertices; ++i) {
outDegree[i] = adjList[i].size();
}
// 遍历邻接表,计算入度
for (int i = 0; i < numVertices; ++i) {
for (int j : adjList[i]) {
inDegree[j]++;
}
}
// 输出每个顶点的入度和出度
for (int i = 0; i < numVertices; ++i) {
std::cout << "顶点 " << i << " 的入度: " << inDegree[i] << ", 出度: " << outDegree[i] << std::endl;
}
}
int main() {
// 示例邻接表表示的有向无环图
std::vector<std::vector<int>> adjList = {
{1, 2}, // 邻接顶点列表表示从顶点0出发的边
{3}, // 邻接顶点列表表示从顶点1出发的边
{3}, // 邻接顶点列表表示从顶点2出发的边
{} // 没有从顶点3出发的边
};
// 计算并输出每个顶点的入度和出度
computeDegrees(adjList);
return 0;
}
```
这段代码中,`computeDegrees`函数接收一个邻接表`adjList`作为参数,该邻接表表示图的各个顶点和它们的邻接顶点。函数内部使用两个向量`inDegree`和`outDegree`来分别存储每个顶点的入度和出度。通过遍历邻接表,可以计算出每个顶点的入度和出度,并打印出来。
阅读全文