考研笔记

板子：DFS 与 BFS（邻接矩阵 + 邻接表）

两种遍历都靠 visited[] 保证每个顶点只访问一次。**DFS 用递归（相当于一个隐式的栈），BFS 用队列。**换一种存储结构，只需要换「怎么找邻接点」那一行。

邻接矩阵版

bool visited[MAXV];                          // 访问标记：全局数组，每次遍历前要清零
 
void DFS_M(MGraph &G, int v) {               // 从 v 出发深度优先
    printf("%d ", v);                        // 访问 v（这里输出顶点下标）
    visited[v] = true;                       // 访问完立刻标记
    for (int w = 0; w < G.numVertices; w++)  // 按下标从小到大找 v 的邻接点
        if (G.Edge[v][w] != 0 && !visited[w])    // 有边，而且还没访问过
            DFS_M(G, w);
}
 
void BFS_M(MGraph &G, int v) {               // 从 v 出发广度优先
    int q[MAXV], front = 0, rear = 0;        // 每个顶点只入队一次，队列开 MAXV 就够
    printf("%d ", v);
    visited[v] = true;                       // 入队时就标记
    q[rear++] = v;
    while (front < rear) {
        int u = q[front++];
        for (int w = 0; w < G.numVertices; w++)
            if (G.Edge[u][w] != 0 && !visited[w]) {
                printf("%d ", w);            // 访问、标记、入队，三件事一起做
                visited[w] = true;
                q[rear++] = w;
            }
    }
}
 
void DFSTraverse(MGraph &G) {                // 非连通图：每个连通分量都要出发一次
    for (int i = 0; i < G.numVertices; i++) visited[i] = false;
    for (int i = 0; i < G.numVertices; i++)
        if (!visited[i]) DFS_M(G, i);        // 无向图里，这一行执行几次就有几个连通分量
}

邻接表版

void DFS_L(ALGraph &G, int v) {
    printf("%d ", v);
    visited[v] = true;
    for (ArcNode *p = G.vertices[v].firstarc; p != NULL; p = p->nextarc)   // 沿边表逐条看 v 的边
        if (!visited[p->adjvex]) DFS_L(G, p->adjvex);
}
 
void BFS_L(ALGraph &G, int v) {
    int q[MAXV], front = 0, rear = 0;
    printf("%d ", v);
    visited[v] = true;
    q[rear++] = v;
    while (front < rear) {
        int u = q[front++];
        for (ArcNode *p = G.vertices[u].firstarc; p != NULL; p = p->nextarc) {
            int w = p->adjvex;               // 这条边指向的顶点
            if (!visited[w]) {
                printf("%d ", w);
                visited[w] = true;
                q[rear++] = w;
            }
        }
    }
}

复杂度（ 个顶点， 条边）：

邻接矩阵邻接表
时间：每个顶点都要扫一整行：每条边只看一次
空间：visited 加上递归栈或队列

关键边界

位置为什么
BFS 在入队时标记如果出队时才标记，一个顶点可能被好几个邻居重复入队
每次遍历前把 visited 清零它是全局数组，不清零的话第二次遍历什么都访问不到
DFSTraverse 的外层循环非连通图从一个顶点出发走不完所有顶点
遍历序列是否唯一邻接矩阵版按下标顺序找邻接点，序列唯一；邻接表版取决于边表里的顺序，所以教材说「基于邻接表的遍历序列不唯一」

易错点

  • 这里的矩阵是 0/1 矩阵，有边写成 G.Edge[v][w] != 0。换成带权矩阵（没有边存 INF，对角线为 0）时，要改成 w != v && G.Edge[v][w] < INF。
  • 教材的 BFS / DFS 伪代码用 FirstNeighbor / NextNeighbor 找邻接点，以此和存储结构解耦。考场上直接写成上面的循环，更清楚。

链接

反向链接