邻接表转化为逆邻接表c代码
时间: 2023-10-14 16:20:46 浏览: 39
下面是将邻接表转化为逆邻接表的C代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 邻接表节点
struct AdjListNode {
int dest;
struct AdjListNode* next;
};
// 邻接表
struct AdjList {
struct AdjListNode* head;
};
// 图
struct Graph {
int num_vertices;
struct AdjList* adj_list;
};
// 创建邻接表节点
struct AdjListNode* create_adj_list_node(int dest) {
struct AdjListNode* new_node = (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
new_node->dest = dest;
new_node->next = NULL;
return new_node;
}
// 添加边
void add_edge(struct Graph* graph, int src, int dest) {
struct AdjListNode* new_node = create_adj_list_node(dest);
new_node->next = graph->adj_list[src].head;
graph->adj_list[src].head = new_node;
}
// 创建图
struct Graph* create_graph(int num_vertices) {
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->num_vertices = num_vertices;
graph->adj_list = (struct AdjList*) malloc(num_vertices * sizeof(struct AdjList));
for (int i = 0; i < num_vertices; i++) {
graph->adj_list[i].head = NULL;
}
return graph;
}
// 逆邻接表节点
struct InvAdjListNode {
int src;
struct InvAdjListNode* next;
};
// 逆邻接表
struct InvAdjList {
struct InvAdjListNode* head;
};
// 创建逆邻接表节点
struct InvAdjListNode* create_invadj_list_node(int src) {
struct InvAdjListNode* new_node = (struct InvAdjListNode*) malloc(sizeof(struct InvAdjListNode));
new_node->src = src;
new_node->next = NULL;
return new_node;
}
// 将邻接表转化为逆邻接表
struct InvAdjList* convert_adjlist_to_invadjlist(struct Graph* graph) {
struct InvAdjList* invadj_list = (struct InvAdjList*) malloc(graph->num_vertices * sizeof(struct InvAdjList));
// 初始化逆邻接表
for (int i = 0; i < graph->num_vertices; i++) {
invadj_list[i].head = NULL;
}
// 遍历邻接表中的每个顶点和相邻顶点
for (int i = 0; i < graph->num_vertices; i++) {
struct AdjListNode* curr_node = graph->adj_list[i].head;
while (curr_node != NULL) {
// 添加该顶点到相邻顶点的逆邻接表中
struct InvAdjListNode* new_node = create_invadj_list_node(i);
new_node->next = invadj_list[curr_node->dest].head;
invadj_list[curr_node->dest].head = new_node;
curr_node = curr_node->next;
}
}
return invadj_list;
}
// 打印逆邻接表
void print_invadjlist(struct InvAdjList* invadj_list, int num_vertices) {
for (int i = 0; i < num_vertices; i++) {
printf("顶点 %d 被以下顶点相邻:", i);
struct InvAdjListNode* curr_node = invadj_list[i].head;
while (curr_node != NULL) {
printf("%d ", curr_node->src);
curr_node = curr_node->next;
}
printf("\n");
}
}
int main() {
// 创建图
struct Graph* graph = create_graph(4);
add_edge(graph, 0, 1);
add_edge(graph, 0, 2);
add_edge(graph, 1, 2);
add_edge(graph, 2, 0);
add_edge(graph, 2, 3);
add_edge(graph, 3, 3);
// 将邻接表转化为逆邻接表
struct InvAdjList* invadj_list = convert_adjlist_to_invadjlist(graph);
// 打印逆邻接表
print_invadjlist(invadj_list, graph->num_vertices);
return 0;
}
```
这个代码实现了邻接表和逆邻接表的创建以及将邻接表转化为逆邻接表的操作。最后将逆邻接表打印出来,以验证转化是否正确。