给出一个无向图(无重边/自环),请你计算每个顶点的度。
时间: 2024-10-19 19:13:14 浏览: 73
数据结构实验3
在无向图中,每个顶点的度是指与其相连的边的数量。对于给定的无向图,没有重复边和自环意味着每个顶点连接的边都是独特的。要计算每个顶点的度,你可以遍历所有的边,并为每个端点增加1,表示每条边都贡献了度数。
以下是一个简单的C++代码示例,使用邻接列表(vector-of-vector)来存储无向图:
```cpp
#include <iostream>
#include <vector>
// 定义图中的节点
using namespace std;
struct Node {
int id; // 顶点ID
vector<int> neighbors; // 邻居顶点ID的集合
};
// 计算节点的度
int degree(const Node& node) {
return node.neighbors.size();
}
// 主函数用于演示如何计算所有顶点的度
void calculate_degrees(Node graph[], int num_vertices) {
for (int i = 0; i < num_vertices; ++i) {
cout << "Degree of vertex " << i << ": " << degree(graph[i]) << endl;
}
}
int main() {
Node graph[] = { // 假设我们有一个5个顶点的图
{0, {1, 3}}, // 顶点0与顶点1和3相连
{1, {}}, // 顶点1没有邻居(度为0)
{2, {0, 4}}, // 顶点2与顶点0和4相连
{3, {0, 2}}, // 顶点3与顶点0和2相连
{4, {2}} // 顶点4只与顶点2相连
};
int num_vertices = sizeof(graph) / sizeof(graph[0]);
calculate_degrees(graph, num_vertices);
return 0;
}
```
运行这段代码后,你会看到每个顶点的度数。请注意,这个例子假设图的数据结构已经正确地反映了图的结构。如果你有具体图的表示,请提供相应的数据结构或邻接矩阵,我可以帮助你编写对应的计算程序。
阅读全文