用C语言实现输入无向图的顶点数、边数及各条边的顶点对,建立用邻接表表示的无向图。
时间: 2024-03-15 16:44:36 浏览: 77
好的,这是一个比较复杂的问题,但我会尽力回答。首先,我们需要定义一个邻接表的结构体,用于表示无向图的结构:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义邻接表结构体
typedef struct node {
int vertex; // 顶点的编号
struct node* next; // 指向下一个相邻结点的指针
} Node;
// 定义图的结构体
typedef struct graph {
int V; // 图的顶点数
int E; // 图的边数
Node** adj_list; // 邻接表
} Graph;
```
接下来,我们需要实现一个函数,用于创建一个邻接表表示的无向图。该函数需要读取用户输入的顶点数、边数以及各条边的顶点对,并将它们添加到邻接表中。
```c
// 创建无向图的邻接表
Graph* create_graph() {
Graph* G = (Graph*)malloc(sizeof(Graph));
if (G == NULL) {
printf("Memory Error!");
return NULL;
}
printf("Enter the number of vertices: ");
scanf("%d", &G->V);
printf("Enter the number of edges: ");
scanf("%d", &G->E);
G->adj_list = (Node**)malloc(sizeof(Node*) * G->V);
for (int i = 0; i < G->V; i++) {
G->adj_list[i] = NULL;
}
int u, v;
for (int i = 0; i < G->E; i++) {
printf("Enter edge %d (u v): ", i+1);
scanf("%d %d", &u, &v);
Node* node1 = (Node*)malloc(sizeof(Node));
node1->vertex = v;
node1->next = G->adj_list[u];
G->adj_list[u] = node1;
Node* node2 = (Node*)malloc(sizeof(Node));
node2->vertex = u;
node2->next = G->adj_list[v];
G->adj_list[v] = node2;
}
return G;
}
```
最后,我们需要实现一个函数,用于打印邻接表表示的无向图。
```c
// 打印无向图的邻接表
void print_graph(Graph* G) {
printf("Adjacency List:\n");
for (int i = 0; i < G->V; i++) {
printf("%d: ", i);
Node* node = G->adj_list[i];
while (node != NULL) {
printf("%d -> ", node->vertex);
node = node->next;
}
printf("NULL\n");
}
}
```
完整的代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义邻接表结构体
typedef struct node {
int vertex; // 顶点的编号
struct node* next; // 指向下一个相邻结点的指针
} Node;
// 定义图的结构体
typedef struct graph {
int V; // 图的顶点数
int E; // 图的边数
Node** adj_list; // 邻接表
} Graph;
// 创建无向图的邻接表
Graph* create_graph() {
Graph* G = (Graph*)malloc(sizeof(Graph));
if (G == NULL) {
printf("Memory Error!");
return NULL;
}
printf("Enter the number of vertices: ");
scanf("%d", &G->V);
printf("Enter the number of edges: ");
scanf("%d", &G->E);
G->adj_list = (Node**)malloc(sizeof(Node*) * G->V);
for (int i = 0; i < G->V; i++) {
G->adj_list[i] = NULL;
}
int u, v;
for (int i = 0; i < G->E; i++) {
printf("Enter edge %d (u v): ", i+1);
scanf("%d %d", &u, &v);
Node* node1 = (Node*)malloc(sizeof(Node));
node1->vertex = v;
node1->next = G->adj_list[u];
G->adj_list[u] = node1;
Node* node2 = (Node*)malloc(sizeof(Node));
node2->vertex = u;
node2->next = G->adj_list[v];
G->adj_list[v] = node2;
}
return G;
}
// 打印无向图的邻接表
void print_graph(Graph* G) {
printf("Adjacency List:\n");
for (int i = 0; i < G->V; i++) {
printf("%d: ", i);
Node* node = G->adj_list[i];
while (node != NULL) {
printf("%d -> ", node->vertex);
node = node->next;
}
printf("NULL\n");
}
}
int main() {
Graph* G = create_graph();
print_graph(G);
return 0;
}
```
希望能对你有所帮助!
阅读全文