用C语言实现并能运行:输入无向图的顶点数、边数及各条边的顶点对,建立用邻接表表示的无向图。
时间: 2024-03-15 14:44:00 浏览: 68
邻接表存储的有向图的基本操作(C语言实现)
好的,我可以为您提供代码实现。以下是用C语言实现输入无向图的顶点数、边数及各条边的顶点对,建立用邻接表表示的无向图的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 邻接表存储结构
typedef struct node {
int data; // 顶点编号
struct node* next; // 指向下一个邻接点的指针
} Node;
// 无向图结构体
typedef struct graph {
int v_num; // 顶点数
int e_num; // 边数
Node** adj; // 存储邻接表的数组
} Graph;
// 创建新节点
Node* new_node(int data) {
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->next = NULL;
return node;
}
// 在邻接表中添加新节点
void add_node(Node** adj, int src, int dest) {
Node* node = new_node(dest);
node->next = adj[src];
adj[src] = node;
}
// 创建无向图
Graph* create_graph(int v_num, int e_num) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->v_num = v_num;
graph->e_num = e_num;
graph->adj = (Node**)malloc(v_num * sizeof(Node*));
// 初始化邻接表为空
for (int i = 0; i < v_num; ++i) {
graph->adj[i] = NULL;
}
// 添加边到邻接表
for (int i = 0; i < e_num; ++i) {
int src, dest;
printf("请输入第 %d 条边的顶点对(例如:1 2):", i + 1);
scanf("%d %d", &src, &dest);
add_node(graph->adj, src, dest);
add_node(graph->adj, dest, src); // 无向图需要添加两次
}
return graph;
}
// 打印邻接表
void print_graph(Graph* graph) {
for (int i = 0; i < graph->v_num; ++i) {
printf("顶点 %d 的邻接表:", i);
Node* node = graph->adj[i];
while (node) {
printf(" %d", node->data);
node = node->next;
}
printf("\n");
}
}
int main() {
int v_num, e_num;
printf("请输入无向图的顶点数和边数(例如:5 7):");
scanf("%d %d", &v_num, &e_num);
Graph* graph = create_graph(v_num, e_num);
printf("无向图建立成功!\n");
print_graph(graph);
return 0;
}
```
您可以将上述代码保存为一个文件,例如 `graph.c`,然后使用 C 语言编译器进行编译,例如使用 GCC 编译器可以使用以下命令:
```
gcc graph.c -o graph
```
然后运行程序即可:
```
./graph
```
程序会提示您输入无向图的顶点数和边数,以及每条边的顶点对。程序会创建一个邻接表表示的无向图,并打印出每个顶点的邻接表。
阅读全文