输入无向图的顶点数、边数及各条边的顶点对,用c语言建立用邻接表表示的无向图,并举例
时间: 2024-02-15 10:05:41 浏览: 64
好的,以下是用C语言建立无向图的邻接表表示的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
struct Node {
int dest;
struct Node* next;
};
struct Graph {
int V;
struct Node** adjList;
};
struct Node* createNode(int dest) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
struct Graph* createGraph(int V) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
graph->adjList = (struct Node**)malloc(V * sizeof(struct Node*));
for (int i = 0; i < V; i++) {
graph->adjList[i] = NULL;
}
return graph;
}
void addEdge(struct Graph* graph, int src, int dest) {
struct Node* newNode = createNode(dest);
newNode->next = graph->adjList[src];
graph->adjList[src] = newNode;
newNode = createNode(src);
newNode->next = graph->adjList[dest];
graph->adjList[dest] = newNode;
}
void printGraph(struct Graph* graph) {
for (int i = 0; i < graph->V; i++) {
struct Node* ptr = graph->adjList[i];
printf("\n Adjacency list of vertex %d\n head ", i);
while (ptr != NULL) {
printf("-> %d", ptr->dest);
ptr = ptr->next;
}
printf("\n");
}
}
int main() {
int V, E;
printf("Enter the number of vertices in the graph: ");
scanf("%d", &V);
struct Graph* graph = createGraph(V);
printf("Enter the number of edges in the graph: ");
scanf("%d", &E);
for (int i = 0; i < E; i++) {
int src, dest;
printf("Enter edge %d: ", i+1);
scanf("%d %d", &src, &dest);
addEdge(graph, src, dest);
}
printGraph(graph);
return 0;
}
```
假设我们要建立以下无向图:
```
(0)
/ \
/ \
(1)---(2)
| |
| |
(3)---(4)
```
我们可以输入以下数据来构建该无向图:
```
Enter the number of vertices in the graph: 5
Enter the number of edges in the graph: 6
Enter edge 1: 0 1
Enter edge 2: 0 2
Enter edge 3: 1 2
Enter edge 4: 1 3
Enter edge 5: 2 4
Enter edge 6: 3 4
```
运行程序后,将会输出以下结果:
```
Adjacency list of vertex 0
head -> 1-> 2
Adjacency list of vertex 1
head -> 0-> 2-> 3
Adjacency list of vertex 2
head -> 0-> 1-> 4
Adjacency list of vertex 3
head -> 1-> 4
Adjacency list of vertex 4
head -> 2-> 3
```
可以看到,该程序成功地建立了用邻接表表示的无向图,并输出了每个顶点的邻接点列表。
阅读全文