邻接表转化逆邻接表c语言
时间: 2023-08-24 11:20:58 浏览: 55
以下是邻接表转化为逆邻接表的 C 语言代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100
typedef struct ArcNode {
int adjvex; // 邻接点在顶点数组中的位置下标
struct ArcNode *nextarc; // 指向下一个邻接点
} ArcNode;
typedef struct VNode {
int data; // 顶点数据
ArcNode *firstarc; // 指向第一个邻接点
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices; // 存储图的顶点和邻接表
int vexnum, arcnum; // 顶点数和边数
} ALGraph;
// 初始化图
void initGraph(ALGraph *G, int n, int m) {
G->vexnum = n;
G->arcnum = m;
for (int i = 0; i < n; i++) {
G->vertices[i].data = i; // 顶点编号从0开始
G->vertices[i].firstarc = NULL;
}
}
// 添加边
void addEdge(ALGraph *G, int u, int v) {
ArcNode *node = (ArcNode *) malloc(sizeof(ArcNode));
node->adjvex = u; // 注意这里是逆邻接表
node->nextarc = G->vertices[v].firstarc;
G->vertices[v].firstarc = node;
}
// 打印邻接表
void printGraph(ALGraph G) {
for (int i = 0; i < G.vexnum; i++) {
printf("%d: ", G.vertices[i].data);
ArcNode *p = G.vertices[i].firstarc;
while (p != NULL) {
printf("%d ", p->adjvex);
p = p->nextarc;
}
printf("\n");
}
}
int main() {
int n = 4, m = 5;
ALGraph G;
initGraph(&G, n, m);
addEdge(&G, 0, 1);
addEdge(&G, 1, 0);
addEdge(&G, 1, 2);
addEdge(&G, 2, 0);
addEdge(&G, 3, 1);
printGraph(G);
return 0;
}
```
在上面的代码中,我们通过 `addEdge` 函数向逆邻接表中添加边。最后通过 `printGraph` 函数打印出逆邻接表。注意逆邻接表中的每个节点都存储了一个该节点指向的顶点的下标,这和邻接表中存储的是该节点的邻接点的下标是相反的。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)