用c++实现有一个邻接表存储的图G,分别设计实现以下要求的算法:求出图中每个顶点的出度,计算图中出度为0的顶点数
时间: 2024-03-05 19:54:59 浏览: 65
好的,以下是用C++实现上述算法的代码:
```c++
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
void findOutdegree(unordered_map<int, vector<int>> graph) {
unordered_map<int, int> outdegree; // 存储每个顶点的出度
int zero_outdegree_count = 0; // 出度为0的顶点数量
// 初始化每个顶点的出度为0
for (auto vertex : graph) {
outdegree[vertex.first] = 0;
}
// 计算每个顶点的出度
for (auto vertex : graph) {
for (auto adjacent_vertex : vertex.second) {
outdegree[vertex.first]++;
}
}
// 统计出度为0的顶点数量
for (auto vertex : graph) {
if (outdegree[vertex.first] == 0) {
zero_outdegree_count++;
}
}
// 输出结果
cout << "每个顶点的出度:\n";
for (auto vertex : outdegree) {
cout << vertex.first << " " << vertex.second << "\n";
}
cout << "出度为0的顶点数量:" << zero_outdegree_count << "\n";
}
int main() {
// 构建一个邻接表表示的图
unordered_map<int, vector<int>> graph = {
{1, {2, 3}},
{2, {3, 4}},
{3, {4}},
{4, {1}},
{5, {}}
};
findOutdegree(graph);
return 0;
}
```
其中,graph为邻接表表示的图,unordered_map类型,键为顶点,值为相邻顶点列表。
您可以将您自己的邻接表输入该算法进行测试。希望能够帮助到您!
阅读全文