c++写有一个邻接表存储的图G,分别设计实现以下要求的算法:求出图中每个顶点的出度;计算图中出度为0的顶点数。
时间: 2024-03-16 22:44:53 浏览: 67
试写一个算法,在以邻接矩阵方式储存的有向图G中求顶点i到顶点j的不含回路的长度为k的路径数
4星 · 用户满意度95%
好的,针对您的问题,我可以给出以下的算法实现:
1. 求出图中每个顶点的出度:
算法实现:
```c++
// 邻接表存储的图结构体
struct Graph {
int n; // 顶点数
vector<vector<int>> adj; // 邻接表
};
// 计算每个顶点的出度
vector<int> calcOutDegree(const Graph& G) {
vector<int> outDegree(G.n, 0);
for (int u = 0; u < G.n; ++u) {
for (int v : G.adj[u]) {
++outDegree[u];
}
}
return outDegree;
}
```
2. 计算图中出度为0的顶点数:
算法实现:
```c++
// 计算出度为0的顶点数
int countZeroOutDegree(const Graph& G) {
int cnt = 0;
for (int u = 0; u < G.n; ++u) {
if (G.adj[u].empty()) { // 邻接表为空,即出度为0
++cnt;
}
}
return cnt;
}
```
以上就是两个算法的实现,您可以根据实际情况进行调用。
阅读全文