图出现环代码(实战篇)

背景

有时候要处理图出现首位相连的代码。下面的java代码就是传入的参数，key为source,value为下一个节点的集合。

    public static <T> Map<T, Set<T>> removeCycles(Map<T, Set<T>> graph) {
        // Make a deep copy of the graph to avoid modifying the original map.
        Map<T, Set<T>> graphCopy = new HashMap<>();
        for (Map.Entry<T, Set<T>> entry : graph.entrySet()) {
            graphCopy.put(entry.getKey(), new HashSet<>(entry.getValue()));
        }

        // Use DFS to detect and remove cycles.
        Set<T> onPath = new HashSet<>();
        for (T node : graphCopy.keySet()) {
            dfs(node, graphCopy, onPath);
        }

        return graphCopy;
    }

    private static <T> boolean dfs(T node, Map<T, Set<T>> graph, Set<T> onPath) {
        // Mark the current node as being on the path.
        onPath.add(node);

        // Get the set of neighbors for the current node.
        Set<T> neighbors = graph.get(node);
        if (neighbors != null) {
            // Iterate over each neighbor.
            Iterator<T> iterator = neighbors.iterator();
            while (iterator.hasNext()) {
                T neighbor = iterator.next();
                // If the neighbor is already on the path, we have found a cycle.
                if (onPath.contains(neighbor)) {
                    // Remove the edge that forms part of the cycle.
                    iterator.remove();
                } else {
                    // Recursively check for cycles in the neighbor's subgraph.
                    if (dfs(neighbor, graph, onPath)) {
                        // A cycle was detected, so remove this edge.
                        iterator.remove();
                    }
                }
            }
        }

        // Backtrack: remove the current node from the path.
        onPath.remove(node);

        // No cycle was detected from this node.
        return false;
    }