图的遍历

广度优先搜索(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+e),邻接矩阵 O(n2)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+e),邻接矩阵 O(n2)O(n^2)。

习题

习题 1

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

深度优先搜索广度优先搜索图遍历时间复杂度

解题思路:

本题考查两种图遍历算法的思想与实现。思路是先说明两者的访问次序差别(纵深优先 vs 按层推进),再分别指出它们对应的实现结构,最后比较时间复杂度。

详细步骤:

  1. DFS(深度优先搜索):从某顶点出发,优先访问纵深方向的邻接点,到尽头后回溯,用递归(栈)实现,类似树的前序遍历。
  2. BFS(广度优先搜索):从某顶点出发,先访问所有邻接点,再访问邻接点的邻接点,用队列实现,类似树的层序遍历。
  3. 两者的时间复杂度相同:邻接表表示下为 O(n+e)O(n+e),邻接矩阵表示下为 O(n2)O(n^2)。

最终答案:

DFS(深度优先搜索):从某顶点出发,优先访问纵深方向的邻接点,到尽头后回溯,用递归(栈)实现,类似树的前序遍历。BFS(广度优先搜索):从某顶点出发,先访问所有邻接点,再访问邻接点的邻接点,用队列实现,类似树的层序遍历。两者的时间复杂度相同:邻接表 O(n+e),邻接矩阵 O(n²)。

发现内容有问题?

告诉我们哪里需要改进。