版本比较
比较
标识
- 该行被添加。
- 该行被删除。
- 格式已经改变。
广度优先遍历
先访问当前结点,再访问所有未被访问的邻接点,再依次从这些邻接点出发,继续访问未被访问的邻接点。
广度优先遍历需要借助队列实现,由于每个结点只需要访问一次,而图可能存在环,所以需要设置一个visited
数组,用于记录当前结点是否被访问过。
算法步骤:
- 定义一个空的队列,初始化
visited
数组,初始时全部结点都未被访问。 - 从图中某一顶点
u
出现,访问u
并标记u
已访问,将u
入队。 - 循环检测队列是否为空,如果不为空,则队头元素
v
出队,依次访问v
所有未被访问的邻接点,标记已访问并入队,直到队列为空。
基于邻接矩阵的BFS代码:
代码块 |
---|
int graph[MAXN][MAXN]; // 邻接表
int n; // 顶点数
bool visited[MAXN]; // 记录顶点是否已访问
void BFS_AM(int u) { // 邻接矩阵BFS,起点为u
queue<int> Q;
cout << u << " ";
visited[u] = true;
Q.push(u);
while(!Q.empty()) {
int v = Q.front();
Q.pop();
for(int i = 0; i < n; i++) { // 依次检查v的所有邻接点
if(graph[v][i] && !visited[i]) { // v、i相邻且i未被访问
cout << i << " ";
visited[i] = true;
Q.push(i);
}
}
}
} |
基于邻接表的BFS代码:
代码块 |
---|
深度优先遍历
目录 |
---|