使用c++语言求采用邻接表作为有向图的存储结构的有向图各顶点的入度
时间: 2023-06-19 13:03:44 浏览: 47
首先,我们需要定义一个邻接表的结构体来存储有向图:
```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 是邻接表的数组,每个元素表示一个顶点的邻接表。
接下来,我们可以编写一个函数来计算每个顶点的入度:
```c++
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。最后返回一个存储各个顶点入度的向量。
完整代码如下:
```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) {}
};
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
```