图的遍历

广度优先搜索（BFS）

从起始顶点出发，先访问其所有邻接点，再依次访问邻接点的邻接点，借助队列实现，类似树的层序遍历。

bool visited[MAX];
void BFS(ALGraph G, int v) {
    InitQueue(Q);
    visit(v);
    visited[v] = true;
    EnQueue(Q, v);
    while (!QueueEmpty(Q)) {
        DeQueue(Q, v);
        for (ArcNode *p = G.vertices[v].first; p; p = p->next) {
            if (!visited[p->adjvex]) {
                visit(p->adjvex);
                visited[p->adjvex] = true;
                EnQueue(Q, p->adjvex);
            }
        }
    }
}

复杂度：邻接表 $O(n+e)$，邻接矩阵 $O(n^2)$。

深度优先搜索（DFS）

从起始顶点出发，一直访问到尽头再回溯，借助**递归（栈）**实现，类似树的前序遍历。

void DFS(ALGraph G, int v) {
    visit(v);
    visited[v] = true;
    for (ArcNode *p = G.vertices[v].first; p; p = p->next) {
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex);  // 递归访问未访问的邻接点
        }
    }
}

复杂度：邻接表 $O(n+e)$，邻接矩阵 $O(n^2)$。

习题

习题 1

DFS 和 BFS 的基本思想和实现方式是什么？