檢測連續添加邊緣的在線圖形中的週期？

Question

如何在有向圖中檢測一個循環，其中邊相繼添加。 如果在循環創建中添加最新的邊緣結果，則不應添加該邊緣。

上述問題的最佳解決方案是什麼？

Answer 1

在有向圖，假設你是從u增加一個邊緣到v：

你必須檢查是否V和U已經連接。您可以使用BFS或DFS來做到這一點。

如果您確定存在從v到u的連接，則從u到v添加邊將導致一個循環。

對於演示，我已經從互聯網上實現了一個圖形，並添加了路徑是否存在從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); 

    } 
} 

Answer 2

的簡單算法，然後會像：

1. 遍歷圖形（BFS將做的工作）
2. 在探索的節點，標誌着它像「好吧，我去過那裏」。你可以使用一些HashSet來做到這一點。
3. 如果節點已經在一個集合中，那麼你第二次來到它，所以有一個循環 - 你可以安全地返回'這個圖形有一個循環'的答案。

現在給出一個狀態爲X（當前狀態）的圖沒有循環，它們在頂點A→B之間添加一個新的邊時可以創建一個新的循環。但在這種情況下，A將永遠是這種循環的一部分。因此重新開始A遍歷是有意義的。根據圖的大小和性質，您可以更快地找到它。

希望這有助於

Answer 3

算法對於這個問題仍是一個研究課題，但對於許多實際情況下，它有很大幫助你添加邊維持支配樹的圖（https://en.wikipedia.org/wiki/Dominator_(graph_theory)）。

維護統治者樹可以完成每個添加操作的分期O（log（V + E））時間，或者可能更好一點。

當你添加一條邊時，你仍然需要做一個DFS或BFS，但是由於一個循環中的所有頂點都經過了同一個直接控制器，所以你只需要搜索那些將是同一個父代子代的頂點，父母本身，在支配樹中檢測該週期。

如果在構建圖形時不允許循環，則可能會有很多支配點，並且您必須搜索每個邊緣插入的節點數量很小。