版本比较
比较
标识
- 该行被添加。
- 该行被删除。
- 格式已经改变。
广度优先遍历
先访问当前结点,再访问所有未被访问的邻接点,再依次从这些邻接点出发,继续访问未被访问的邻接点。
广度优先遍历需要借助队列实现,由于每个结点只需要访问一次,而图可能存在环,所以需要设置一个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代码:
代码块 |
---|
vector<int> graph[MAXN]; // 邻接表
int n; // 顶点数
bool visited[MAXN]; // 记录顶点是否已访问
void BFS_AL(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(auto &i : graph[v]) { // 依次检查v的所有邻接点
if(!visited[i]) {
cout << i << " ";
visited[i] = true;
Q.push(i);
}
}
}
} |
深度优先遍历
沿着一条路径一直走下去,直到无法进行时,回退到上一步,看有没有还还未被访问的邻接点,重复前面的操作。
深度优先遍历需要借助栈来实现,也可以直接使用递归来实现,因为递归本身就是使用栈来实现的。同样需要设置visited数组,以保证每个结点只被访问一次。
算法步骤:
- 初始化全部的结点为未访问状态。
- 从图中的某个顶点
u
出发,访问u
并标记已访问。 - 依次检查
u
的所有邻接点v,如果v
未被访问,则从v
出现继续深度优先遍历。
基于邻接矩阵的DFS代码:
代码块 |
---|
void DFS_AM(int u) {
cout << u << " ";
visited[u] = true;
for(int i = 0; i < n; i++) {
if(graph[u][i] && !visited[i]) {
DFS_AM(i);
}
}
} |
基于邻接表的DFS代码:
代码块 |
---|
void DFS_AL(int u) {
cout << u << " ";
visited[u] = true;
for(auto &i : graph[u]) {
if(!visited[i]) {
DFS_AL(i);
}
}
} |
目录 |
---|