统计有向图中每个顶点的出度和入度并打印
时间: 2023-04-17 12:02:45 浏览: 181
可以使用邻接矩阵或邻接表来表示有向图。对于邻接矩阵,每个顶点的出度可以通过计算该顶点所在行的非零元素个数得到,入度可以通过计算该顶点所在列的非零元素个数得到。对于邻接表,每个顶点的出度可以通过计算该顶点对应链表的长度得到,入度可以通过遍历整个邻接表,统计每个顶点在其他顶点的链表中出现的次数得到。最后,将每个顶点的出度和入度打印出来即可。
相关问题
c语言求有向图中每个顶点的入度和出度
对于一个有向图,每个顶点的入度和出度可以通过遍历图中所有的边来计算。
1. 入度:对于每个顶点,遍历所有的边,统计指向该顶点的边的数量即为该顶点的入度。
2. 出度:对于每个顶点,遍历所有的边,统计从该顶点出发的边的数量即为该顶点的出度。
具体的代码实现可以参考下面的示例:
```c
#include <stdio.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
// 边的结构体
typedef struct {
int tail; // 起点
int head; // 终点
} Arc;
// 有向图的结构体
typedef struct {
Arc arcs[MAX_VERTEX_NUM]; // 存储所有边的数组
int indegree[MAX_VERTEX_NUM]; // 存储每个顶点的入度
int outdegree[MAX_VERTEX_NUM]; // 存储每个顶点的出度
int vexnum; // 顶点数
int arcnum; // 边数
} Graph;
// 初始化有向图
void initGraph(Graph *G) {
int i;
for (i = 0; i < G->vexnum; i++) {
G->indegree[i] = 0;
G->outdegree[i] = 0;
}
}
// 计算每个顶点的入度和出度
void calcDegree(Graph *G) {
int i;
for (i = 0; i < G->arcnum; i++) {
int tail = G->arcs[i].tail;
int head = G->arcs[i].head;
G->outdegree[tail]++;
G->indegree[head]++;
}
}
int main() {
Graph G;
int i;
printf("请输入顶点数和边数:");
scanf("%d%d", &G.vexnum, &G.arcnum);
printf("请依次输入每条边的起点和终点:\n");
for (i = 0; i < G.arcnum; i++) {
scanf("%d%d", &G.arcs[i].tail, &G.arcs[i].head);
}
initGraph(&G);
calcDegree(&G);
printf("每个顶点的入度和出度分别为:\n");
for (i = 0; i < G.vexnum; i++) {
printf("顶点%d:入度%d,出度%d\n", i, G.indegree[i], G.outdegree[i]);
}
return 0;
}
```
这里我们用结构体表示有向图,包括顶点数、边数、边的数组以及每个顶点的入度和出度数组。然后通过遍历边的数组,统计每个顶点的入度和出度,最后输出每个顶点的入度和出度即可。
算法设计求有向图中每个顶点的入度和出度
好的,根据您的要求,我来为您编写这个算法。
假设有向图的邻接表存储结构如下:
```
typedef struct ArcNode {
int adjvex; // 邻接点在顶点数组中的下标
struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;
typedef struct VNode {
int data; // 顶点的数据
ArcNode *firstarc; // 指向第一个邻接点的指针
int indegree; // 顶点的入度
int outdegree; // 顶点的出度
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices; // 存储各个顶点的邻接表
int vexnum, arcnum; // 图的顶点数和弧数
} ALGraph;
```
1. 求每个顶点的入度
对于有向图中的每个顶点,可以遍历整个邻接表,统计指向该顶点的弧的条数,即为该顶点的入度。具体算法如下:
```
void indegree(ALGraph *G) {
// 初始化每个顶点的入度为0
for (int i = 0; i < G->vexnum; i++) {
G->vertices[i].indegree = 0;
}
// 遍历整个邻接表,统计每个顶点的入度
for (int i = 0; i < G->vexnum; i++) {
ArcNode *p = G->vertices[i].firstarc;
while (p != NULL) {
G->vertices[p->adjvex].indegree++;
p = p->nextarc;
}
}
}
```
2. 求每个顶点的出度
对于有向图中的每个顶点,可以遍历该顶点的邻接表,统计该顶点指向其他顶点的弧的条数,即为该顶点的出度。具体算法如下:
```
void outdegree(ALGraph *G) {
// 初始化每个顶点的出度为0
for (int i = 0; i < G->vexnum; i++) {
G->vertices[i].outdegree = 0;
}
// 遍历每个顶点的邻接表,统计每个顶点的出度
for (int i = 0; i < G->vexnum; i++) {
ArcNode *p = G->vertices[i].firstarc;
while (p != NULL) {
G->vertices[i].outdegree++;
p = p->nextarc;
}
}
}
```
希望能够帮助到您!