帮我用C语言写一份代码,要求是:自己输入创建一个邻接表,实现广度优先遍历
时间: 2024-02-13 13:06:31 浏览: 77
好的,以下是一个使用C语言实现自己输入创建邻接表,并实现广度优先遍历的示例代码:
```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_NODES 100
// 邻接表结点
typedef struct AdjListNode {
int dest;
struct AdjListNode* next;
} AdjListNode;
// 邻接表
typedef struct AdjList {
AdjListNode* head;
} AdjList;
bool visited[MAX_NODES];
int queue[MAX_NODES];
int front = 0, rear = 0;
// 创建邻接表结点
AdjListNode* createNode(int dest) {
AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// 添加边到邻接表
void addEdge(AdjList* adjList, int src, int dest) {
AdjListNode* newNode = createNode(dest);
newNode->next = adjList[src].head;
adjList[src].head = newNode;
}
// 广度优先遍历
void bfs(AdjList* adjList, int nodes, int start) {
visited[start] = true;
queue[rear++] = start;
while (front < rear) {
int curr = queue[front++];
printf("%d ", curr);
AdjListNode* temp = adjList[curr].head;
while (temp) {
int neighbor = temp->dest;
if (!visited[neighbor]) {
visited[neighbor] = true;
queue[rear++] = neighbor;
}
temp = temp->next;
}
}
}
int main() {
int nodes, edges, start;
// 读入图的节点数、边数和起点
printf("请输入节点数、边数和起点:");
scanf("%d %d %d", &nodes, &edges, &start);
// 创建邻接表
AdjList adjList[nodes];
for (int i = 0; i < nodes; i++) {
adjList[i].head = NULL;
}
// 读入边并添加到邻接表
printf("请输入每条边的起点和终点:\n");
for (int i = 0; i < edges; i++) {
int u, v;
scanf("%d %d", &u, &v);
addEdge(adjList, u, v);
addEdge(adjList, v, u); // 无向图需要添加反向边
}
// 初始化visited数组
for (int i = 0; i < nodes; i++) {
visited[i] = false;
}
// 调用BFS函数
bfs(adjList, nodes, start);
return 0;
}
```
以上代码中,`AdjListNode` 是邻接表的结点结构体,包含一个 `dest` 字段表示目标节点的编号,和一个 `next` 字段指向下一个邻接节点。`AdjList` 是邻接表结构体,包含一个 `head` 字段指向该节点的第一个邻接节点。`visited` 数组用于记录每个节点是否被访问过。`queue` 数组用于存储待访问的节点。BFS算法的核心是 `bfs` 函数,它从起点 `start` 开始遍历图。在遍历过程中,每访问一个节点都将其标记为已访问,并将其相邻的未访问节点加入队列。在队列中,先加入的节点先被访问,保证了按照距离递增的顺序遍历图。在 `main` 函数中,首先读入图的节点数、边数和起点,并根据输入创建邻接表。然后初始化visited数组,并调用BFS函数进行遍历。
阅读全文