编写使用邻接表存储图信息并使用 BFS 求解最短路径的 C 语言代码:
时间: 2023-09-19 21:06:43 浏览: 137
### 回答1:
首先,我们需要定义一个链表结构体来存储图中的每个点:
```
struct ListNode {
int val; // 点的编号
int weight; // 边的权值
struct ListNode* next; // 指向下一个邻接点的指针
};
```
然后,我们可以定义一个链表数组来存储图中所有点的邻接表:
```
struct ListNode* adj[MAX_VERTICES];
```
其中 `MAX_VERTICES` 是图中点的最大数量。
然后,我们可以使用队列实现 BFS 算法:
```
// 初始化队列和访问数组
int visited[MAX_VERTICES];
for (int i = 0; i < numVertices; i++) {
visited[i] = 0;
}
// 初始化距离数组
int distance[MAX_VERTICES];
for (int i = 0; i < numVertices; i++) {
distance[i] = -1;
}
// 初始化队列
struct Queue* queue = createQueue();
// 将起点加入队列
enqueue(queue, start);
visited[start] = 1;
distance[start] = 0;
while (!isEmpty(queue)) {
// 从队列中取出一个点
int curr = dequeue(queue);
// 遍历该点的所有邻接点
struct ListNode* temp = adj[curr];
while (temp) {
int neighbor = temp->val;
// 如果没有被访问过,就加入队列
if (!visited[neighbor]) {
enqueue(queue, neighbor);
visited[neighbor] = 1;
distance[neighbor] = distance[curr] + 1;
}
temp = temp->next;
}
}
```
在上面的代码中,`start` 是起点的编号,`numVertices` 是图中点的数量,`createQueue` 函数用于创
### 回答2:
下面是一个使用邻接表存储图信息并使用BFS求解最短路径的C语言代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_NODES 100
// 邻接表节点
typedef struct Node {
int vertex;
struct Node* next;
} Node;
// 邻接表
typedef struct AdjList {
Node* head;
} AdjList;
// 图结构
typedef struct Graph {
int numNodes;
AdjList* adjLists[MAX_NODES];
} Graph;
// 创建图节点
Node* createNode(int v) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
// 创建图
Graph* createGraph(int numNodes) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->numNodes = numNodes;
for (int i = 0; i < numNodes; i++) {
graph->adjLists[i] = (AdjList*)malloc(sizeof(AdjList));
graph->adjLists[i]->head = NULL;
}
return graph;
}
// 添加边
void addEdge(Graph* graph, int src, int dest) {
Node* newNode = createNode(dest);
newNode->next = graph->adjLists[src]->head;
graph->adjLists[src]->head = newNode;
newNode = createNode(src);
newNode->next = graph->adjLists[dest]->head;
graph->adjLists[dest]->head = newNode;
}
// 广度优先搜索
void bfs(Graph* graph, int startNode, int endNode) {
bool visited[MAX_NODES];
for (int i = 0; i < graph->numNodes; i++) {
visited[i] = false;
}
int queue[MAX_NODES];
int front = 0, rear = 0;
visited[startNode] = true;
queue[rear++] = startNode;
while (front != rear) {
int current = queue[front++];
printf("%d ", current);
if (current == endNode) {
break;
}
Node* temp = graph->adjLists[current]->head;
while (temp) {
int vertex = temp->vertex;
if (!visited[vertex]) {
visited[vertex] = true;
queue[rear++] = vertex;
}
temp = temp->next;
}
}
}
int main() {
int numNodes = 6;
Graph* graph = createGraph(numNodes);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
addEdge(graph, 3, 5);
int startNode = 0;
int endNode = 5;
printf("最短路径:");
bfs(graph, startNode, endNode);
return 0;
}
```
这段代码首先定义了邻接表的数据结构,然后使用`createGraph`函数创建图,并使用`addEdge`函数添加边。最后,使用`bfs`函数进行广度优先搜索来查找从`startNode`到`endNode`的最短路径,最短路径上的节点将被依次打印出来。
### 回答3:
下面是使用邻接表存储图信息并使用 BFS 求解最短路径的 C 语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 邻接表的节点结构
struct Node {
int dest; // 目标顶点
struct Node* next; // 指向下一个节点
};
// 图的结构
struct Graph {
int V; // 图中顶点的数量
struct Node** adj; // 邻接表
};
// 创建节点
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->adj = (struct Node**)malloc(V * sizeof(struct Node*));
for (int i = 0; i < V; ++i) {
graph->adj[i] = NULL;
}
return graph;
}
// 添加边
void addEdge(struct Graph* graph, int src, int dest) {
// 添加边 src -> dest
struct Node* newNode = createNode(dest);
newNode->next = graph->adj[src];
graph->adj[src] = newNode;
// 添加边 dest -> src
newNode = createNode(src);
newNode->next = graph->adj[dest];
graph->adj[dest] = newNode;
}
// BFS 求最短路径
void bfs(struct Graph* graph, int src, int dest) {
// 判断顶点是否被访问过
int* visited = (int*)malloc(graph->V * sizeof(int));
for (int i = 0; i < graph->V; ++i) {
visited[i] = 0;
}
// 创建队列
struct Queue* queue = createQueue();
// 将起始顶点标记为已访问并入队
visited[src] = 1;
enqueue(queue, src);
// 用于存储路径
int* parent = (int*)malloc(graph->V * sizeof(int));
for (int i = 0; i < graph->V; ++i) {
parent[i] = -1;
}
// BFS
while (!isEmpty(queue)) {
// 出队并打印
int current = dequeue(queue);
struct Node* temp = graph->adj[current];
while (temp != NULL) {
int adjacent = temp->dest;
if (visited[adjacent] == 0) {
visited[adjacent] = 1;
enqueue(queue, adjacent);
parent[adjacent] = current;
}
temp = temp->next;
}
}
// 打印最短路径
printf("最短路径为: ");
printShortestPath(parent, dest);
}
// 打印最短路径
void printShortestPath(int* parent, int dest) {
if (parent[dest] == -1) {
printf("%d ", dest);
return;
}
printShortestPath(parent, parent[dest]);
printf("%d ", dest);
}
int main() {
int V = 6;
struct Graph* graph = createGraph(V);
addEdge(graph, 0, 1);
addEdge(graph, 1, 2);
addEdge(graph, 2, 3);
addEdge(graph, 0, 4);
addEdge(graph, 4, 5);
addEdge(graph, 1, 5);
int src = 0, dest = 3;
bfs(graph, src, dest);
return 0;
}
```
这段代码实现了使用邻接表存储图信息,并通过 BFS(宽度优先搜索)求解最短路径问题。其中,createNode、createGraph、addEdge 分别用于创建节点、创建图和添加边。bfs 函数通过 BFS 访问图中的顶点,并使用队列来保存将要访问的顶点。printShortestPath 函数用于打印最短路径。在 main 函数中,我们创建了一个包含 6 个顶点的图,并假设起点是顶点 0,终点是顶点 3,通过调用 bfs 函数求解最短路径并打印结果。
阅读全文