考研笔记

板子：判断路径、判断有环、判断树

三个题都是 DFS 的变形：判路径就是看从 出发能不能走到 ；有向图判环要区分「正在访问」和「已经访问完」；判树就是连通而且边数等于 。

代码

bool existPath(MGraph &G, int i, int j) {    // i 到 j 是否有路径；调用前把 visited 全部清零
    if (i == j) return true;                 // 走到了
    visited[i] = true;
    for (int w = 0; w < G.numVertices; w++)
        if (G.Edge[i][w] != 0 && !visited[w] && existPath(G, w, j))
            return true;                     // 从某个邻接点能走到 j，就一路返回 true
    return false;
}
 
int color[MAXV];                             // 0：还没访问；1：正在访问（还在递归栈里）；2：已经访问完
 
bool dfsCycle(MGraph &G, int v) {            // 从 v 出发，看能不能找到环
    color[v] = 1;
    for (int w = 0; w < G.numVertices; w++)
        if (G.Edge[v][w] != 0) {
            if (color[w] == 1) return true;  // 走回了递归栈里的顶点：出现回边，有环
            if (color[w] == 0 && dfsCycle(G, w)) return true;
        }
    color[v] = 2;                            // v 能到的顶点都走完了，没发现环
    return false;
}
 
bool hasCycleDG(MGraph &G) {                 // 有向图是否有环
    for (int i = 0; i < G.numVertices; i++) color[i] = 0;
    for (int i = 0; i < G.numVertices; i++)  // 非连通图：每个没访问过的顶点都要出发一次
        if (color[i] == 0 && dfsCycle(G, i)) return true;
    return false;
}
 
int dfsCount(MGraph &G, int v) {             // 从 v 出发能访问到的顶点个数
    visited[v] = true;
    int cnt = 1;                             // v 自己
    for (int w = 0; w < G.numVertices; w++)
        if (G.Edge[v][w] != 0 && !visited[w]) cnt += dfsCount(G, w);
    return cnt;
}
 
bool isTree(MGraph &G) {                     // 无向图是一棵树 ⇔ 连通，而且边数 = n - 1
    int n = G.numVertices, e = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)      // 无向图的每条边在矩阵里出现两次，只数上三角
            if (G.Edge[i][j] != 0) e++;
    if (e != n - 1) return false;
    for (int i = 0; i < n; i++) visited[i] = false;
    return dfsCount(G, 0) == n;              // 从 0 出发能走遍所有顶点，就是连通的
}

visited[] 用的是 DFS 与 BFS 里定义的全局数组。

复杂度：邻接矩阵上都是时间 ，空间 。

关键边界：有向图判环为什么要三种颜色

碰到的邻接点 说明处理
color[w] == 0还没访问过递归下去
color[w] == 1 还在递归栈里，是 的祖先， 是一条回边有环
color[w] == 2 已经访问完，只是从另一条路又走到了它不是环，跳过

只用 visited 两种状态会误判。例如 、、：访问完 1、2 以后，从 0 再看到 2，2 已经访问过了，但这里没有环。

其他判环方法

  • 有向图：用 拓扑排序，输出的顶点不足 个就有环。
  • 无向图：DFS 时碰到一个已访问、而且不是自己双亲的顶点，就有环。也可以直接数边：无向图无环当且仅当 边数 连通分量数。

易错点

  • existPath 调用前要把 visited 清零，否则上一次遍历的标记会让它提前返回 false。
  • isTree 只数上三角。数整个矩阵的话，边数会多一倍。

链接

反向链接