c语言基于邻接表存储有向图的广度优先遍历
时间: 2023-10-08 21:10:57 浏览: 51
首先,我们需要定义邻接表和队列的结构体。
```
// 定义邻接表结构体
typedef struct node {
int vertex; // 存储顶点编号
struct node* next; // 指向下一个邻接点的指针
} Node;
// 定义队列结构体
typedef struct queue {
int front; // 队首指针
int rear; // 队尾指针
int size; // 队列长度
int capacity; // 队列容量
int* data; // 存储队列元素的指针
} Queue;
```
然后,我们需要实现广度优先遍历算法的函数。该函数以邻接表和起始顶点作为参数,返回遍历结果。
```
// 广度优先遍历算法
void bfs(Node** graph, int start, int* visited, int n) {
Queue* q = createQueue(n); // 创建队列
visited[start] = 1; // 标记起始顶点已被访问
enqueue(q, start); // 将起始顶点入队
while (!isEmpty(q)) {
int v = dequeue(q); // 出队一个顶点
printf("%d ", v); // 输出该顶点
Node* p = graph[v]; // 获取该顶点的邻接表头结点
while (p != NULL) {
int w = p->vertex; // 获取该顶点的邻接点
if (!visited[w]) { // 如果该邻接点未被访问
visited[w] = 1; // 标记该邻接点已被访问
enqueue(q, w); // 将该邻接点入队
}
p = p->next; // 继续遍历该顶点的邻接表
}
}
}
```
其中,`graph`表示邻接表,`start`表示起始顶点,`visited`表示顶点是否被访问的数组,`n`表示顶点数量。函数中使用了队列来实现广度优先遍历。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)