广度优先遍历

先访问当前结点，再访问所有未被访问的邻接点，再依次从这些邻接点出发，继续访问未被访问的邻接点。

广度优先遍历需要借助队列实现，由于每个结点只需要访问一次，而图可能存在环，所以需要设置一个visited数组，用于记录当前结点是否被访问过。

算法步骤：

  1. 定义一个空的队列，初始化visited数组，初始时全部结点都未被访问。
  2. 从图中某一顶点u出现，访问u并标记u已访问，将u入队。
  3. 循环检测队列是否为空，如果不为空，则队头元素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数组，以保证每个结点只被访问一次。

算法步骤：

  1. 初始化全部的结点为未访问状态。
  2. 从图中的某个顶点u出发，访问u并标记已访问。
  3. 依次检查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);
        }
    }
}













  • 无标签