c++写有一个邻接表存储的图G,分别设计实现以下要求的算法:求出图中每个顶点的出度;计算图中出度为0的顶点数。

好的，针对您的问题，我可以给出以下的算法实现：

1. 求出图中每个顶点的出度：

算法实现：

// 邻接表存储的图结构体
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的顶点数：

算法实现：

// 计算出度为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;
}

以上就是两个算法的实现，您可以根据实际情况进行调用。

相关问题

用c++写有一个邻接表存储的图G，分别设计实现以下要求的算法：求出图中每个顶点的出度；计算图中出度为0的顶点数

以下是C++代码实现：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 定义邻接表存储的图
    int n = 5;  // 图的顶点数
    vector<vector<int>> G(n, vector<int>());
    G[0].push_back(1);  // 添加边
    G[0].push_back(2);
    G[1].push_back(3);
    G[2].push_back(1);
    G[2].push_back(3);
    G[3].push_back(4);
    G[4].push_back(2);

    // 求出每个顶点的出度
    vector<int> outdegree(n, 0);
    for (int i = 0; i < n; i++) {
        outdegree[i] = G[i].size();
    }
    cout << "每个顶点的出度为：";
    for (int i = 0; i < n; i++) {
        cout << outdegree[i] << " ";
    }
    cout << endl;

    // 计算出度为0的顶点数
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (outdegree[i] == 0) {
            cnt++;
        }
    }
    cout << "出度为0的顶点数为：" << cnt << endl;

    return 0;
}

上述代码中，首先定义了一个邻接表存储的图，然后用一个二维数组 G 来表示，其中 G[i] 表示节点 i 的所有邻居节点。接着，定义一个长度为 n 的一维数组 outdegree，用来存储每个顶点的出度。遍历邻接表，求出每个节点的出度。最后，再遍历一遍 outdegree 数组，计算出度为0的顶点数。

用c++写有一个邻接表存储的图G，分别设计实现以下要求的算法：求出图中每个顶点的出度，计算图中出度为0的顶点数

好的，以下是用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类型，键为顶点，值为相邻顶点列表。

您可以将您自己的邻接表输入该算法进行测试。希望能够帮助到您！