使用C++编写函数，求邻接矩阵存储结构的有向图G中各顶点的入度。

在C++中，如果你有一个邻接矩阵表示的有向图G，你可以通过遍历矩阵来计算每个顶点的入度。邻接矩阵是一个二维数组，其中`matrix[i][j]`表示从顶点i到顶点j是否有边。为了计算入度，你需要一个单独的数组`degrees`来存储每个顶点的入度值，初始时所有顶点的入度都设为0。

下面是一个简单的示例函数：

#include <vector>

// 函数声明，返回一个整数类型的向量，表示图中每个顶点的入度
std::vector<int> getInDegrees(const std::vector<std::vector<int>>& matrix) {
    int numVertices = matrix.size(); // 图的顶点数
    std::vector<int> degrees(numVertices, 0); // 初始化入度数组

    // 遍历矩阵，对每个节点增加其出边指向的所有节点的计数
    for (int i = 0; i < numVertices; ++i) {
        for (int j = 0; j < numVertices; ++j) {
            if (matrix[i][j] > 0) { // 如果存在从i到j的边
                degrees[j]++;
            }
        }
    }

    return degrees;
}

相关问题

使用c++语言求采用邻接表作为有向图的存储结构的有向图各顶点的入度

首先，我们需要定义一个邻接表的结构体来存储有向图：

#include <iostream>
#include <vector>

using namespace std;

struct Node {
    int val;
    Node* next;
    Node(int _val) : val(_val), next(nullptr) {}
};

struct Graph {
    int V;
    vector<Node*> adjList;
    Graph(int _V) : V(_V), adjList(_V, nullptr) {}
};

其中，Node 表示邻接表中的节点，val 存储节点的值，next 存储下一个节点的指针。Graph 表示有向图，V 表示图中顶点的个数，adjList 是邻接表的数组，每个元素表示一个顶点的邻接表。

接下来，我们可以编写一个函数来计算每个顶点的入度：

vector<int> calculateIndegree(Graph& graph) {
    vector<int> indegree(graph.V, 0);
    for (int i = 0; i < graph.V; i++) {
        Node* cur = graph.adjList[i];
        while (cur) {
            indegree[cur->val]++;
            cur = cur->next;
        }
    }
    return indegree;
}

这个函数的思路是，遍历每个顶点的邻接表，对于邻接表中的每个节点都将其对应的入度加 1。最后返回一个存储各个顶点入度的向量。

完整代码如下：

#include <iostream>
#include <vector>

using namespace std;

struct Node {
    int val;
    Node* next;
    Node(int _val) : val(_val), next(nullptr) {}
};

struct Graph {
    int V;
    vector<Node*> adjList;
    Graph(int _V) : V(_V), adjList(_V, nullptr) {}
};

vector<int> calculateIndegree(Graph& graph) {
    vector<int> indegree(graph.V, 0);
    for (int i = 0; i < graph.V; i++) {
        Node* cur = graph.adjList[i];
        while (cur) {
            indegree[cur->val]++;
            cur = cur->next;
        }
    }
    return indegree;
}

int main() {
    Graph graph(6);
    graph.adjList[0] = new Node(1);
    graph.adjList[0]->next = new Node(2);
    graph.adjList[1] = new Node(3);
    graph.adjList[2] = new Node(3);
    graph.adjList[2]->next = new Node(4);
    graph.adjList[3] = new Node(5);
    graph.adjList[4] = new Node(5);

    vector<int> indegree = calculateIndegree(graph);
    for (int i = 0; i < graph.V; i++) {
        cout << "Vertex " << i << " indegree: " << indegree[i] << endl;
    }

    return 0;
}

输出结果为：

Vertex 0 indegree: 0
Vertex 1 indegree: 1
Vertex 2 indegree: 1
Vertex 3 indegree: 2
Vertex 4 indegree: 1
Vertex 5 indegree: 2

基于有向图的邻接表存储结构实现求顶点入度的函数的代码。用c++实现

下面是基于有向图的邻接表存储结构实现求顶点入度的函数的 C++ 代码：

#include <iostream>
#include <vector>

using namespace std;

// 定义图的邻接表存储结构
struct Graph {
    int V;  // 图的顶点数
    vector<vector<int>> adj;  // 存储每个顶点的出边
};

// 求图中每个顶点的入度
vector<int> findInDegrees(Graph& G) {
    vector<int> inDegrees(G.V, 0);  // 初始每个顶点入度为0

    // 统计每个顶点的入度
    for (int v = 0; v < G.V; ++v) {
        for (int u : G.adj[v]) {
            ++inDegrees[u];
        }
    }

    return inDegrees;
}

int main() {
    // 创建一个有向图
    Graph G;
    G.V = 5;
    G.adj = {{1, 2}, {3}, {3, 4}, {4}, {}};

    // 求每个顶点的入度
    vector<int> inDegrees = findInDegrees(G);

    // 输出每个顶点的入度
    for (int v = 0; v < G.V; ++v) {
        cout << "Vertex " << v << " has in-degree " << inDegrees[v] << endl;
    }

    return 0;
}

在这个代码中，我们首先定义了一个结构体 `Graph` 来存储有向图的邻接表表示，其中 `V` 表示图的顶点数，`adj` 是一个 `vector` 数组，其中 `adj[v]` 存储了顶点 `v` 的所有出边。

然后我们实现了一个函数 `findInDegrees`，该函数接收一个 `Graph` 对象作为参数，并返回一个 `vector` 数组，其中第 `i` 个元素表示顶点 `i` 的入度。在函数内部，我们遍历每个顶点的出边，统计每个顶点的入度，并将结果保存在一个 `vector` 数组中返回。

最后，在 `main` 函数中，我们创建了一个有向图，并调用 `findInDegrees` 函数求出每个顶点的入度，并将结果输出。