编写有向图的广度优先遍历函数
时间: 2023-06-22 22:21:05 浏览: 52
以下是Python语言实现的有向图的广度优先遍历函数:
```python
from collections import deque
def bfs(graph, start):
visited = set() # 用集合存储已经访问过的节点
queue = deque() # 用双向队列实现队列,存储待访问节点
queue.append(start)
visited.add(start)
while queue:
node = queue.popleft() # 取出队首节点
print(node) # 访问节点
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor) # 将未访问过的邻居加入队列
visited.add(neighbor) # 标记邻居为已访问
```
其中,`graph` 为有向图的邻接表表示,`start` 为起始节点。函数利用双向队列实现广度优先遍历,将待访问的节点加入队列中,每次访问队首节点并将其邻居加入队列中。`visited` 集合用来记录已经访问过的节点,避免重复访问。
相关问题
有向图邻接表的广度优先遍历
邻接表是一种表示图的常见数据结构,它通过链表的方式存储每个顶点的相邻顶点。广度优先遍历是一种基于队列的遍历方式,从图的某一起始顶点开始,依次访问其相邻顶点,然后再依次访问相邻顶点的相邻顶点,直到遍历完整个图。
下面是邻接表的广度优先遍历的实现步骤:
1. 初始化一个队列,将起始顶点入队。
2. 初始化一个 visited 数组,用于记录每个顶点是否被访问过,将起始顶点标记为已访问。
3. 当队列不为空时,执行以下步骤:
a. 出队队头元素,并访问该顶点。
b. 遍历该顶点的所有邻接顶点,如果邻接顶点未被访问,则将其入队,并标记为已访问。
4. 重复步骤 3,直到队列为空,遍历结束。
下面是邻接表的广度优先遍历的代码实现(假设图的顶点从 0 到 n-1 编号):
```python
from collections import deque
def bfs(adj_list, start):
n = len(adj_list)
visited = [False] * n
q = deque()
q.append(start)
visited[start] = True
while q:
v = q.popleft()
print(v, end=' ')
for u in adj_list[v]:
if not visited[u]:
q.append(u)
visited[u] = True
```
其中,adj_list 是邻接表,是一个列表的列表,adj_list[i] 表示顶点 i 的邻接顶点列表。start 是起始顶点的编号。函数中使用了 Python 自带的 deque 类型实现队列。
请用C语言编写函数对用邻接矩阵表示的有向图进行广度优先遍历
以下是对用邻接矩阵表示的有向图进行广度优先遍历的C语言函数实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef struct {
int vertex[MAX_VERTEX_NUM]; // 存放顶点信息
int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存放边信息,0表示无边,1表示有边
int vertex_num; // 顶点数
int arc_num; // 边数
} Graph;
// 初始化图
void init_graph(Graph *g) {
int i, j;
printf("请输入图的顶点数和边数(用空格隔开):");
scanf("%d %d", &(g->vertex_num), &(g->arc_num));
printf("请输入图的顶点信息:");
for (i = 0; i < g->vertex_num; i++) {
scanf("%d", &(g->vertex[i]));
}
for (i = 0; i < g->vertex_num; i++) {
for (j = 0; j < g->vertex_num; j++) {
g->arc[i][j] = 0;
}
}
printf("请输入图的边信息(用空格隔开):\n");
for (i = 0; i < g->arc_num; i++) {
int start, end;
scanf("%d %d", &start, &end);
g->arc[start][end] = 1;
}
}
// 广度优先遍历
void bfs(Graph *g, int start) {
int visited[MAX_VERTEX_NUM] = {0}; // 记录每个顶点是否被访问过
int queue[MAX_VERTEX_NUM]; // 队列
int front = -1, rear = -1; // 队列的头尾指针
int i, v;
visited[start] = 1; // 标记起始顶点为已访问
printf("%d ", g->vertex[start]); // 访问起始顶点
queue[++rear] = start; // 将起始顶点入队
while (front != rear) { // 当队列不为空时
v = queue[++front]; // 取出队列头顶点
for (i = 0; i < g->vertex_num; i++) { // 遍历该顶点的所有邻接顶点
if (g->arc[v][i] == 1 && !visited[i]) { // 如果该顶点与当前顶点有边且未被访问过
visited[i] = 1; // 标记该顶点为已访问
printf("%d ", g->vertex[i]); // 访问该顶点
queue[++rear] = i; // 将该顶点入队
}
}
}
}
int main() {
Graph g;
init_graph(&g);
printf("广度优先遍历的结果为:");
bfs(&g, 0); // 从顶点0开始进行广度优先遍历
printf("\n");
return 0;
}
```
其中,`Graph`结构体表示图,包括顶点信息、边信息、顶点数和边数等。`init_graph`函数用于初始化图,包括输入顶点信息、边信息等。`bfs`函数实现广度优先遍历,其中使用队列来存储待访问的顶点。在遍历过程中,每次取出队列头顶点,并访问它的所有邻接顶点,将未访问过的邻接顶点入队。最后,`main`函数中调用`init_graph`函数初始化图,并从顶点0开始进行广度优先遍历,输出遍历结果。