基于邻接表的广度优先
时间: 2023-11-27 13:47:10 浏览: 77
基于邻接表的广度优先搜索可以通过以下步骤实现:
1. 创建一个空队列,将起始节点入队。
2. 创建一个空集合,用于存储已经访问过的节点。
3. 当队列不为空时,执行以下操作:
- 从队列中取出一个节点,记为current。
- 如果current没有被访问过,则将其标记为已访问,并将其所有邻居节点加入队列中。
4. 重复步骤3,直到队列为空。
下面是一个基于邻接表的广度优先搜索的Python实现:
```python
from collections import deque
def bfs(graph, start):
queue = deque([start])
visited = set([start])
while queue:
node = queue.popleft()
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
```
其中,graph是邻接表表示的图,start是起始节点。这个函数会依次输出遍历到的节点。
相关问题
基于邻接表的深度优先遍历
基于邻接表的深度优先遍历(Depth-First Search, DFS)是一种图遍历算法,在遍历过程中,从某个顶点开始,深度优先遍历会优先访问它的任意一个未被访问过的邻居顶点,然后递归地继续访问该邻居顶点的未被访问过的邻居顶点,直到所有与该顶点直接或间接相连的顶点都被访问过为止。
基于邻接表的深度优先遍历可以使用递归实现。具体步骤如下:
1. 创建一个标记数组 visited,用于记录每个顶点是否被访问过,初始值都设置为 false。
2. 从某个起始顶点开始,递归遍历其邻接表中的每个未被访问过的邻居顶点,将其标记为已访问,然后递归遍历该邻居顶点的邻接表,直到所有与起始顶点直接或间接相连的顶点都被访问过为止。
下面是基于邻接表的深度优先遍历的 C++ 代码实现:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int N = 100010; // 最大顶点数
vector<int> adj[N]; // 邻接表
bool visited[N]; // 标记数组
// 深度优先遍历函数
void dfs(int u) {
visited[u] = true; // 标记顶点 u 已被访问
cout << u << " "; // 输出顶点 u
for (int i = 0; i < adj[u].size(); i++) { // 遍历顶点 u 的邻接表
int v = adj[u][i]; // 取出顶点 u 的第 i 个邻居顶点 v
if (!visited[v]) { // 如果顶点 v 未被访问过
dfs(v); // 递归访问顶点 v
}
}
}
int main() {
int n, m; // 顶点数和边数
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v; // 边的起点和终点
cin >> u >> v;
adj[u].push_back(v); // 添加一条从 u 到 v 的有向边
adj[v].push_back(u); // 添加一条从 v 到 u 的有向边
}
for (int i = 1; i <= n; i++) {
if (!visited[i]) { // 如果顶点 i 未被访问过
dfs(i); // 从顶点 i 开始深度优先遍历
}
}
return 0;
}
```
在该代码中,变量 adj 表示邻接表,它是一个 vector 的数组,adj[i] 存储顶点 i 的邻接表。变量 visited 是一个 bool 数组,visited[i] 表示顶点 i 是否被访问过。函数 dfs 实现了深度优先遍历,其中参数 u 表示当前访问的顶点。
在主函数中,先读入图的顶点数和边数,然后读入每条边,把邻接表构建出来。最后遍历每个顶点,如果该顶点未被访问过,则从该顶点开始深度优先遍历。
C语言 基于邻接表的广度优先遍历
基于邻接表的广度优先遍历是一种图的遍历算法,它从图的某个顶点开始遍历,先访问该顶点,然后依次访问该顶点的所有邻接点,再依次访问这些邻接点的邻接点,直到遍历完整个图。下面是C语言实现基于邻接表的广度优先遍历的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20 // 最大顶点数
// 邻接表结构体
typedef struct ArcNode {
int adjvex; // 邻接点在顶点数组中的下标
struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;
// 顶点结构体
typedef struct VNode {
char data; // 顶点数据
ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];
// 图结构体
typedef struct {
AdjList vertices; // 顶点数组
int vexnum, arcnum; // 顶点数和边数
} ALGraph;
// 初始化邻接表
void InitGraph(ALGraph *G) {
int i;
G->vexnum = G->arcnum = 0;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
G->vertices[i].firstarc = NULL;
}
}
// 添加边
void AddArc(ALGraph *G, int v, int w) {
ArcNode *p;
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = w;
p->nextarc = G->vertices[v].firstarc;
G->vertices[v].firstarc = p;
}
// 广度优先遍历
void BFS(ALGraph *G, int v) {
int visited[MAX_VERTEX_NUM] = {0}; // 标记数组,用于标记已访问的顶点
int queue[MAX_VERTEX_NUM], front = 0, rear = 0; // 队列,用于存储待访问的顶点
ArcNode *p;
visited[v] = 1; // 标记起始顶点已访问
printf("%c ", G->vertices[v].data); // 访问起始顶点
queue[rear++] = v; // 将起始顶点入队
while (front != rear) { // 队列不为空时循环
v = queue[front++]; // 出队一个顶点
for (p = G->vertices[v].firstarc; p != NULL; p = p->nextarc) { // 遍历该顶点的所有邻接点
if (!visited[p->adjvex]) { // 如果该邻接点未被访问
visited[p->adjvex] = 1; // 标记该邻接点已访问
printf("%c ", G->vertices[p->adjvex].data); // 访问该邻接点
queue[rear++] = p->adjvex; // 将该邻接点入队
}
}
}
}
// 主函数
int main() {
ALGraph G;
int i, v, w;
char data;
InitGraph(&G);
printf("请输入顶点数和边数:");
scanf("%d%d", &G.vexnum, &G.arcnum);
printf("请输入顶点数据:");
for (i = 0; i < G.vexnum; i++) {
scanf(" %c", &data);
G.vertices[i].data = data;
}
printf("请输入边的顶点序号:");
for (i = 0; i < G.arcnum; i++) {
scanf("%d%d", &v, &w);
AddArc(&G, v, w);
AddArc(&G, w, v); // 无向图需要添加反向边
}
printf("广度优先遍历结果:");
BFS(&G, 0); // 从第一个顶点开始遍历
printf("\n");
return 0;
}
```