【算法设计题】计算有向图G中每个结点的入度和出度，第4题（C/C++）
【算法设计题】计算有向图G中每个结点的入度和出度，第4题（C/C++）
命运之光
发布于 2024-08-09 12:36:47
发布于 2024-08-09 12:36:47
代码可运行
运行总次数：0
代码可运行
🌌 2024，每日百字，记录时光，感谢有你，携手前行~
🚀 携手启航，我们一同深入未知的领域，挖掘潜能，让每一步成长都充满意义。
第4题 计算有向图G中每个结点的入度和出度
已知有向图G的邻接表存储方式，计算图G中每个结点的入度和出度。
得分点（必背）
//题解如下：
//边表结点
typedef struct ArcNode {
int adjvex; // 邻接点域，存储该边所指向的顶点的位置
struct ArcNode *nextarc; // 下一个邻接表结点指针域，用于连接其他边表结点
} ArcNode;
// 顶点表结点
typedef struct VexNode {
int data; // 顶点信息域，存储顶点的信息
ArcNode *first; // 指向该顶点所对应的边表结点指针域，用于连接其他顶点
}VNode, AdjList[MAXVEX];
//图的邻接表存储表示
typedef struct {
VexNode adjlist; // 邻接表，存储顶点信息
int vexnum,arcnum; // 顶点数 // 边数
} AGraph;
//计算图G中每一个结点的入度和出度
void count_du(AGraph G){
int in[G.vexnum], out[G.vexnum];
// 初始化入度和出度数组
for(int i = 0; i < G.vexnum; ++i){
in[i] = 0;
out[i] = 0;
}
//遍历每个顶点的邻接表
for(int i = 0; i < G.vexnum; ++i){
ArcNode *P = G.adjlist[i].first;//这块没问题
while(P){
out[i]++;
in[P->adjvex]++;
P = P->nextarc;
}
}
//输出每个结点的入度和出度
for(int i = 0; i < G.vexnum; ++i){
cout << "顶点" << i << "的入度为：" << in[i] << ", 出度为：" << out[i] << endl;
}
}题解：计算有向图G中每个结点的入度和出度
在这个题目中，我们需要计算有向图G中每个结点的入度和出度。有向图的邻接表存储方式由顶点表和边表构成，顶点表存储顶点信息，边表存储边的指向关系。
数据结构定义
边表结点
typedef struct ArcNode {
int adjvex; // 邻接点域，存储该边所指向的顶点的位置
struct ArcNode *nextarc; // 下一个邻接表结点指针域，用于连接其他边表结点
} ArcNode;adjvex：该边所指向的顶点的位置。nextarc：指向下一个边表结点的指针，用于连接同一顶点的其他边。
顶点表结点
typedef struct VexNode {
int data; // 顶点信息域，存储顶点的信息
ArcNode *first; // 指向该顶点所对应的边表结点指针域，用于连接其他顶点
} VNode, AdjList[MAXVEX];data：存储顶点的信息。first：指向该顶点的第一个边表结点。
图的邻接表存储表示
typedef struct {
VexNode adjlist[MAXVEX]; // 邻接表，存储顶点信息
int vexnum, arcnum; // 顶点数和边数
} AGraph;adjlist：邻接表，存储所有顶点的信息。vexnum：顶点数。arcnum：边数。
计算图G中每个结点的入度和出度
void count_du(AGraph G){
int in[G.vexnum], out[G.vexnum];
// 初始化入度和出度数组
for(int i = 0; i < G.vexnum; ++i){
in[i] = 0;
out[i] = 0;
}
// 遍历每个顶点的邻接表
for(int i = 0; i < G.vexnum; ++i){
ArcNode *P = G.adjlist[i].first;
while(P){
out[i]++; // 当前顶点的出度加1
in[P->adjvex]++; // P所指向的顶点的入度加1
P = P->nextarc; // 移动到下一个边表结点
}
}
// 输出每个结点的入度和出度
for(int i = 0; i < G.vexnum; ++i){
cout << "顶点" << i << "的入度为：" << in[i] << ", 出度为：" << out[i] << endl;
}
}详细解释
1. 初始化入度和出度数组
int in[G.vexnum], out[G.vexnum];
for(int i = 0; i < G.vexnum; ++i){
in[i] = 0;
out[i] = 0;
}- 创建两个数组
in和out分别用于存储每个顶点的入度和出度。 - 使用循环将这两个数组初始化为0。
2. 遍历每个顶点的邻接表
for(int i = 0; i < G.vexnum; ++i){
ArcNode *P = G.adjlist[i].first;
while(P){
out[i]++; // 当前顶点的出度加1
in[P->adjvex]++; // P所指向的顶点的入度加1
P = P->nextarc; // 移动到下一个边表结点
}
}- 使用循环遍历图中每个顶点。
- 对于每个顶点，获取其边表的第一个结点。
- 遍历边表的每个结点，统计出度和入度：
- 当前顶点的出度加1。
- 该结点所指向的顶点的入度加1。
- 移动到下一个边表结点。
3. 输出每个结点的入度和出度
for(int i = 0; i < G.vexnum; ++i){
cout << "顶点" << i << "的入度为：" << in[i] << ", 出度为：" << out[i] << endl;
}- 再次使用循环，遍历每个顶点。
- 输出每个顶点的入度和出度。
示例
假设有如下图G：
顶点0 -> 顶点1 -> 顶点2
顶点1 -> 顶点2 -> 顶点3
顶点2 -> 顶点3- 顶点0的出度为1，入度为0。
- 顶点1的出度为2，入度为1。
- 顶点2的出度为1，入度为2。
- 顶点3的出度为0，入度为2。
运行上述代码，输出如下：
顶点0的入度为：0, 出度为：1
顶点1的入度为：1, 出度为：2
顶点2的入度为：2, 出度为：1
顶点3的入度为：2, 出度为：0本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-08-07，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
