入门程序员咨询：如何判断输入节点是否属于图中的环？

嘿，刚入门的程序员同学，我来帮你搞定这个问题～先看你贴的Java代码，这明显是个无向图的实现（addEdge里同时给双向边赋值了），那咱们就针对无向图的场景来拆解解决方案。

核心思路 #

无向图里的环很好识别：在深度优先搜索（DFS）遍历的时候，如果遇到一个已经访问过的节点，而且这个节点不是当前节点的「父节点」（毕竟无向图里父子节点是双向连通的，不能把这个正常的边当成环），那说明咱们找到了环。要判断指定节点是否在环里，咱们只需要从这个节点出发做DFS，看能不能碰到符合上述条件的情况就行。

具体实现（基于你的Graph类） #

直接在你的Graph类里补充两个方法即可：一个对外的公共方法接收目标节点，一个内部递归的DFS方法负责遍历判断。

public class Graph {
    private int nbNodes;
    private boolean[][] adjacency;

    // 你原有的构造方法
    public Graph(int nb){ 
        this.nbNodes = nb; 
        this.adjacency = new boolean [nb][nb]; 
        for (int i = 0; i < nb; i++){ 
            for (int j = 0; j < nb; j++){ 
                this.adjacency[i][j] = false; 
            } 
        } 
    }

    // 你原有的addEdge方法
    public void addEdge (int i, int j){ 
        if(!(i<0 || i>=this.nbNodes|| j<0 || j>=this.nbNodes)) { 
            this.adjacency[i][j] = true; 
            this.adjacency[j][i] = true; 
        } 
    }

    // 补全你未写完的removeEdge方法
    public void removeEdge (int i, int j){ 
        if(!(i<0 || i>=this.nbNodes|| j<0 || j>=this.nbNodes)) { 
            this.adjacency[i][j] = false; 
            this.adjacency[j][i] = false; 
        } 
    }

    // 新增：判断指定节点是否在环中的公共方法
    public boolean isNodeInCycle(int targetNode) {
        // 先校验节点合法性，避免数组越界
        if (targetNode < 0 || targetNode >= nbNodes) {
            throw new IllegalArgumentException("节点索引不合法，请输入0到" + (nbNodes-1) + "之间的数");
        }
        boolean[] visited = new boolean[nbNodes];
        // 从目标节点开始DFS，初始父节点设为-1（起始节点没有父节点）
        return dfs(targetNode, -1, visited);
    }

    // 内部递归DFS方法
    private boolean dfs(int currentNode, int parentNode, boolean[] visited) {
        // 标记当前节点已访问，防止重复遍历
        visited[currentNode] = true;

        // 遍历当前节点的所有邻接节点
        for (int neighbor = 0; neighbor < nbNodes; neighbor++) {
            // 如果当前节点与neighbor之间存在边
            if (adjacency[currentNode][neighbor]) {
                if (!visited[neighbor]) {
                    // 邻接节点未访问过，递归遍历并将当前节点设为父节点
                    if (dfs(neighbor, currentNode, visited)) {
                        return true;
                    }
                } else if (neighbor != parentNode) {
                    // 邻接节点已访问且不是父节点——找到环了！
                    return true;
                }
            }
        }
        // 遍历完所有邻接节点都没找到环，返回false
        return false;
    }
}

代码说明 #

• 合法性校验：先确保输入的目标节点在图的节点范围内，避免出现数组越界异常。
• DFS遍历逻辑：
  1. 标记当前节点为已访问，防止重复处理同一个节点。
  2. 逐个检查当前节点的邻接节点：
     • 如果邻接节点未被访问过，就递归进入该节点继续遍历，同时把当前节点作为它的父节点传递。
     • 如果邻接节点已被访问，且不是父节点，这意味着我们绕回了之前访问过的非父节点——这就是环的特征，直接返回true。
  3. 如果遍历完所有邻接节点都没找到环，说明该节点所在的连通分量中没有环，返回false。

小提示 #

这个方法只适用于无向图（也就是你当前实现的双向边图）。如果以后需要处理有向图，判断节点是否在环里的逻辑会有所不同，需要追踪递归栈中的节点，但那是后续进阶的内容啦～

内容的提问来源于stack exchange，提问作者Matthew Zoltak