c语言函数怎么实现邻接表存储图的广度优先遍历函数
时间: 2023-06-04 20:07:39 浏览: 162
C语言数据结构-邻接表的广度优先遍历
可以使用队列来实现。首先将起始顶点放入队列中,然后按照广度优先的规则,依次遍历与该顶点相邻的顶点,并将它们放入队列中。接着从队列的头部取出下一个顶点,重复上述操作,直到队列为空。以下是C语言代码实现:
```
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
typedef struct _node {
int vertex;
struct _node* next;
} Node;
typedef struct _graph {
Node* list[MAX_VERTICES];
int visited[MAX_VERTICES];
int vertices;
int edges;
} Graph;
void bfs(Graph* graph, int start)
{
Node* node;
int dequeued;
int v;
int queue[MAX_VERTICES];
int front = 0, rear = 0;
for (v = 0; v < graph->vertices; v++) {
graph->visited[v] = 0;
}
graph->visited[start] = 1;
queue[rear++] = start;
while (front < rear) {
dequeued = queue[front++];
printf("%d ", dequeued);
for (node = graph->list[dequeued]; node != NULL; node = node->next) {
if (!graph->visited[node->vertex]) {
graph->visited[node->vertex] = 1;
queue[rear++] = node->vertex;
}
}
}
}
void add_edge(Graph* graph, int from, int to)
{
Node* edge = (Node*)malloc(sizeof(Node));
edge->vertex = to;
edge->next = graph->list[from];
graph->list[from] = edge;
}
int main(void)
{
Graph graph;
int i, v, e, from, to, start;
printf("Enter the number of vertices: ");
scanf("%d", &v);
printf("Enter the number of edges: ");
scanf("%d", &e);
for (i = 0; i < v; i++) {
graph.list[i] = NULL;
}
graph.vertices = v;
graph.edges = e;
for (i = 0; i < e; i++) {
printf("Enter edge %d:\n", i + 1);
scanf("%d %d", &from, &to);
add_edge(&graph, from, to);
}
printf("Enter the starting vertex: ");
scanf("%d", &start);
printf("Breadth First Search: ");
bfs(&graph, start);
return 0;
}
```
该程序将输入的邻接表保存在一个链表数组中,使用visited数组记录每个顶点的访问情况,在遍历的过程中将访问过的顶点加入队列,并将其相邻的顶点加入队列,直到队列为空。
阅读全文