用C语言以邻接表形式创建一个无向图。
时间: 2023-11-24 10:08:22 浏览: 82
创建无向图的邻接表,需要使用链表数据结构,每个节点表示一个顶点,每个节点下面有一个链表,链表中存储该顶点与其他顶点相邻的边。
以下是示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 邻接表节点结构体
typedef struct AdjListNode {
int dest;
struct AdjListNode* next;
} AdjListNode;
// 邻接表头结构体
typedef struct AdjList {
AdjListNode* head;
} AdjList;
// 图结构体
typedef struct Graph {
int num_vertices;
AdjList* adj_lists;
} Graph;
// 创建邻接表节点
AdjListNode* create_adj_list_node(int dest) {
AdjListNode* new_node = (AdjListNode*)malloc(sizeof(AdjListNode));
new_node->dest = dest;
new_node->next = NULL;
return new_node;
}
// 创建图
Graph* create_graph(int num_vertices) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->num_vertices = num_vertices;
// 创建邻接表数组
graph->adj_lists = (AdjList*)malloc(num_vertices * sizeof(AdjList));
// 初始化邻接表头指针为NULL
for (int i = 0; i < num_vertices; i++) {
graph->adj_lists[i].head = NULL;
}
return graph;
}
// 添加边
void add_edge(Graph* graph, int src, int dest) {
// 添加从src到dest的边
AdjListNode* new_node = create_adj_list_node(dest);
new_node->next = graph->adj_lists[src].head;
graph->adj_lists[src].head = new_node;
// 添加从dest到src的边
new_node = create_adj_list_node(src);
new_node->next = graph->adj_lists[dest].head;
graph->adj_lists[dest].head = new_node;
}
// 打印图
void print_graph(Graph* graph) {
for (int i = 0; i < graph->num_vertices; i++) {
AdjListNode* current_node = graph->adj_lists[i].head;
printf("顶点 %d: ", i);
while (current_node) {
printf("%d -> ", current_node->dest);
current_node = current_node->next;
}
printf("NULL\n");
}
}
int main() {
// 创建图
Graph* graph = create_graph(5);
// 添加边
add_edge(graph, 0, 1);
add_edge(graph, 0, 4);
add_edge(graph, 1, 2);
add_edge(graph, 1, 3);
add_edge(graph, 1, 4);
add_edge(graph, 2, 3);
add_edge(graph, 3, 4);
// 打印图
print_graph(graph);
return 0;
}
```
输出结果:
```
顶点 0: 4 -> 1 -> NULL
顶点 1: 4 -> 3 -> 2 -> 0 -> NULL
顶点 2: 3 -> 1 -> NULL
顶点 3: 4 -> 2 -> 1 -> NULL
顶点 4: 3 -> 1 -> 0 -> NULL
```
阅读全文