java - 检测在线图中连续添加边的循环？

Question

如何检测有向图中的环，其中一条边一条接一条地添加。 如果添加最新的边导致循环创建，则不应添加该边。

上述问题的最佳解决方案是什么？

Answer 1

在有向图中，假设您要添加一条从 u 到 v 的边:

你必须检查 v 和 u 是否已经连接。您可以使用 BFS 或 DFS 来做到这一点。

如果您确定从 v 到 u 存在连接，则从 u 到 v 添加一条边将导致循环。

为了Demo，我从网上做了一个图的实现，并添加了从v到u的路径是否存在的逻辑。此逻辑在以下代码中的函数 doesPathExistBetween(V from, V to) 中。

package java8new;

import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class Digraph<V> {

    public static class Edge<V> {
        private V vertex;
        private int cost;

        public Edge(V v, int c) {
            vertex = v;
            cost = c;
        }

        public V getVertex() {
            return vertex;
        }

        public int getCost() {
            return cost;
        }

        @Override
        public String toString() {
            return "Edge [vertex=" + vertex + ", cost=" + cost + "]";
        }

    }

    /**
     * A Map is used to map each vertex to its list of adjacent vertices.
     */

    private Map<V, List<Edge<V>>> neighbors = new HashMap<V, List<Edge<V>>>();

    /**
     * String representation of graph.
     */
    public String toString() {
        StringBuffer s = new StringBuffer();
        for (V v : neighbors.keySet())
            s.append("\n    " + v + " -> " + neighbors.get(v));
        return s.toString();
    }

    /**
     * Add a vertex to the graph. Nothing happens if vertex is already in graph.
     */
    public void add(V vertex) {
        if (neighbors.containsKey(vertex))
            return;
        neighbors.put(vertex, new ArrayList<Edge<V>>());
    }

    /**
     * Add an edge to the graph; if either vertex does not exist, it's added.
     * This implementation allows the creation of multi-edges and self-loops.
     */
    public void add(V from, V to, int cost) {
        this.add(from);
        this.add(to);
        neighbors.get(from).add(new Edge<V>(to, cost));
    }

    public List<V> outboundNeighbors(V vertex) {
        List<V> list = new ArrayList<V>();
        for (Edge<V> e : neighbors.get(vertex))
            list.add(e.vertex);
        return list;
    }

    public void bfs(V root) {
        // Since queue is a interface
        Queue<V> queue = new LinkedList<V>();
        Map<V, Boolean> visited = new HashMap<V, Boolean>();

        if (root == null)
            return;

        visited.put(root, Boolean.TRUE);
        // Adds to end of queue
        queue.add(root);

        while (!queue.isEmpty()) {
            // removes from front of queue
            V r = queue.remove();
            System.out.println(r.toString());

            // Visit child first before grandchild
            for (V n : outboundNeighbors(r)) {
                if (!visited.containsKey(n)) {

                    queue.add(n);
                    visited.put(n, Boolean.TRUE);
                }
            }
        }
    }

    public Boolean doesPathExistBetween(V from, V to) {
        Queue<V> queue = new LinkedList<V>();
        Map<V, Boolean> visited = new HashMap<V, Boolean>();

        visited.put(from, Boolean.TRUE);

        // Adds to end of queue
        queue.add(from);

        while (!queue.isEmpty()) {
            // removes from front of queue
            V r = queue.remove();

            // Visit child first before grandchild
            for (V n : outboundNeighbors(r)) {
                if (!visited.containsKey(n)) {
                    if (n.equals(to))
                        return Boolean.TRUE;
                    queue.add(n);
                    visited.put(n, Boolean.TRUE);
                }
            }
        }
        return Boolean.FALSE;

    }

    public static void main(String[] args) throws IOException {

        Digraph<Integer> graph = new Digraph<Integer>();
        // Adding vertices
        graph.add(0);
        graph.add(1);
        graph.add(2);
        graph.add(3);
        // Adding Edges with weights
        graph.add(0, 1, 1);
        graph.add(1, 2, 2);
        graph.add(3, 0, 2);

        System.out.println("Path betwen 0 to 2 exists : " + graph.doesPathExistBetween(0, 2));
        System.out.println("Path betwen 1 to 3 exists : " + graph.doesPathExistBetween(1, 3));

        graph.bfs(0);
        graph.bfs(1);

    }
}