版本比较
比较
标识
- 该行被添加。
- 该行被删除。
- 格式已经改变。
广度优先遍历
先访问当前结点,再访问所有未被访问的邻接点,再依次从这些邻接点出发,继续访问未被访问的邻接点。
广度优先遍历需要借助队列实现,由于每个结点只需要访问一次,而图可能存在环,所以需要设置一个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代码:
代码块 |
---|
深度优先遍历
要。
目录 |
---|