邻接矩阵C语言表示法中 ArcNode节点的AdjType adj 和OtherInfo info是什么
时间: 2024-05-31 18:09:17 浏览: 15
在邻接矩阵C语言表示法中,ArcNode节点表示图中的一条边。每个ArcNode节点包含三个字段:
- int adj:该边所连接的顶点在顶点数组中的下标。如果该边连接的是顶点数组中的第i个顶点和第j个顶点,则该字段的值为j。
- AdjType info:该边所携带的信息,比如边的权值等。AdjType是一个自定义的数据类型,可以根据需要定义不同的类型。
- ArcNode *next:指向下一条以同一个顶点为起点的边。
其中,adj字段表示该边连接的顶点在顶点数组中的下标,info字段表示该边所携带的信息,比如边的权值等,可以根据需要定义不同的类型。
相关问题
用邻接矩阵法表示法创建无向网 C语言
以下是用邻接矩阵法表示无向网的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef int VertexType; // 顶点类型
typedef int EdgeType; // 边权值类型
typedef struct {
VertexType vexs[MAX_VERTEX_NUM]; // 顶点数组
EdgeType edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vexnum, edgenum; // 顶点数和边数
} MGraph;
// 创建无向网
void CreateUDN(MGraph *G) {
int i, j, k, w;
printf("请输入顶点数和边数:\n");
scanf("%d %d", &G->vexnum, &G->edgenum);
printf("请输入顶点信息:\n");
for (i = 0; i < G->vexnum; i++) {
scanf("%d", &G->vexs[i]);
}
// 初始化邻接矩阵
for (i = 0; i < G->vexnum; i++) {
for (j = 0; j < G->vexnum; j++) {
G->edges[i][j] = INT_MAX;
}
}
// 构造邻接矩阵
for (k = 0; k < G->edgenum; k++) {
printf("请输入边(Vi,Vj)的顶点序号和权值:\n");
scanf("%d %d %d", &i, &j, &w);
G->edges[i][j] = w;
G->edges[j][i] = w; // 无向网,对称赋值
}
}
// 输出邻接矩阵
void PrintGraph(MGraph G) {
int i, j;
printf("顶点信息:\n");
for (i = 0; i < G.vexnum; i++) {
printf("%d ", G.vexs[i]);
}
printf("\n邻接矩阵:\n");
for (i = 0; i < G.vexnum; i++) {
for (j = 0; j < G.vexnum; j++) {
if (G.edges[i][j] == INT_MAX) {
printf("∞ ");
} else {
printf("%d ", G.edges[i][j]);
}
}
printf("\n");
}
}
int main() {
MGraph G;
CreateUDN(&G);
PrintGraph(G);
return 0;
}
```
示例输出:
```
请输入顶点数和边数:
5 7
请输入顶点信息:
1 2 3 4 5
请输入边(Vi,Vj)的顶点序号和权值:
0 1 5
请输入边(Vi,Vj)的顶点序号和权值:
0 2 7
请输入边(Vi,Vj)的顶点序号和权值:
1 2 3
请输入边(Vi,Vj)的顶点序号和权值:
1 3 8
请输入边(Vi,Vj)的顶点序号和权值:
2 4 6
请输入边(Vi,Vj)的顶点序号和权值:
2 3 4
请输入边(Vi,Vj)的顶点序号和权值:
3 4 2
顶点信息:
1 2 3 4 5
邻接矩阵:
∞ 5 7 ∞ ∞
5 ∞ 3 8 ∞
7 3 ∞ 4 6
∞ 8 4 ∞ 2
∞ ∞ 6 2 ∞
```
邻接矩阵表示法计算各个节点的度代码
假设邻接矩阵为 `adj_matrix`,节点数量为 `n`,可以使用以下代码计算每个节点的度:
```python
degree = [0] * n # 初始化每个节点的度为 0
for i in range(n):
for j in range(n):
if adj_matrix[i][j] == 1:
degree[i] += 1 # 节点 i 的度加 1
print(degree) # 输出每个节点的度
```
解释一下上面的代码:
- 我们首先初始化每个节点的度为 0,即 `degree = [0] * n`。
- 然后遍历邻接矩阵的每一个元素,如果发现 `adj_matrix[i][j] == 1`,说明节点 i 和节点 j 之间有一条边,因此节点 i 的度要加 1,即 `degree[i] += 1`。
- 最后输出每个节点的度,即 `print(degree)`。