利用队列实现图的广度优先遍历
时间: 2023-12-05 15:50:52 浏览: 73
使用队列实现图的广度优先遍历的基本思路如下:
1. 将起始顶点放入队列中,并将其标记为已访问。
2. 从队列中取出一个顶点,并访问它的所有邻居顶点。
3. 对于每个未访问的邻居顶点,将其放入队列中,并标记为已访问。
4. 重复步骤2和3,直到队列为空。
以下是使用队列实现图的广度优先遍历的 Python 代码示例:
```
from queue import Queue
def bfs(graph, start):
visited = set()
queue = Queue()
queue.put(start)
visited.add(start)
while not queue.empty():
vertex = queue.get()
print(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
queue.put(neighbor)
visited.add(neighbor)
```
其中,graph 是表示图的邻接表,start 是起始顶点。在遍历过程中,我们使用 visited 集合记录已访问的顶点,避免重复访问。利用队列的先进先出特性,我们可以保证每个顶点都被访问一次,并且按照广度优先的顺序进行遍历。
相关问题
环形队列实现广度优先遍历
环形队列可以用来实现广度优先遍历,具体实现步骤如下:
1. 首先,需要定义一个队列,用来存储待访问的节点。
2. 将起始节点加入队列中,并将其标记为已访问。
3. 当队列不为空时,取出队首节点,并将其所有未访问的邻居节点加入队列中,并标记为已访问。
4. 重复步骤3,直到队列为空。
下面是环形队列实现广度优先遍历的示例代码:
```C++
#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 100; // 最大节点数
int head[MAXN], nxt[MAXN], ver[MAXN], tot = 0; // 邻接表存储图
bool visited[MAXN]; // 标记节点是否被访问过
void add(int x, int y) { // 添加边
ver[++tot] = y;
nxt[tot] = head[x];
head[x] = tot;
}
void bfs(int s) { // 广度优先遍历
queue<int> q;
q.push(s);
visited[s] = true;
while (!q.empty()) {
int x = q.front();
q.pop();
cout << x << " ";
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i];
if (!visited[y]) {
q.push(y);
visited[y] = true;
}
}
}
}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
add(x, y);
add(y, x); // 无向图需要加上反向边
}
bfs(s);
return 0;
}
```
队列图的广度优先遍历c
好的,以下是队列实现的广度优先遍历的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义队列结构体
struct queue {
int data;
struct queue* next;
};
// 全局变量,头结点、尾结点
struct queue* front = NULL;
struct queue* rear = NULL;
// 入队操作
void enqueue(int data) {
struct queue* temp = (struct queue*)malloc(sizeof(struct queue));
temp->data = data;
temp->next = NULL;
if (front == NULL && rear == NULL) {
front = rear = temp;
return;
}
rear->next = temp;
rear = temp;
}
// 出队操作
void dequeue() {
struct queue* temp = front;
if (front == NULL) {
printf("队列已空\n");
return;
}
if (front == rear) {
front = rear = NULL;
} else {
front = front->next;
}
free(temp);
}
// 判断队列是否为空
int is_empty() {
if (front == NULL) {
return 1;
} else {
return 0;
}
}
// 广度优先遍历
void bfs(int G[][7], int start, int n) {
int i = start, j;
int visited[7] = { 0 };
printf("%d ", i);
visited[i] = 1;
enqueue(i);
while (!is_empty()) {
i = front->data;
dequeue();
for (j = 1; j < n; j++) {
if (G[i][j] == 1 && visited[j] == 0) {
printf("%d ", j);
visited[j] = 1;
enqueue(j);
}
}
}
}
int main() {
// 定义邻接矩阵
int G[7][7] = {
{0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 1, 0, 0, 0},
{0, 1, 0, 0, 1, 0, 0},
{0, 1, 0, 0, 1, 0, 0},
{0, 0, 1, 1, 0, 1, 1},
{0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 1, 0, 0}
};
bfs(G, 1, 7);
return 0;
}
```
这里以一个邻接矩阵图为例进行广度优先遍历,如果需要遍历其他类型的图,只需要修改邻接矩阵的表示方法即可。