Google – Print All Cycles in Graph

Google – Print All Cycles in Graph
很简单的题，但是对于是否会出现无限循环？或者发现cycle后要不要把visit[]置1（表示已经结束）？这两个想来想去想不清楚的问题，赤裸裸的证明了我recursion和backtracking根本就没想明白过….
首先会不会出现无限循环？
答案是no. 不会出现无限循环. 因为如果找到了一个cycle，也就是回到了某个visit过但是还没有结束的vertex，我们做的是输出cycle后return，而不是继续往下找，如果继续往下找就会出现无限循环了。所以无论图里有几个cycle，都不会出现无限循环的情况。
其次要不要置1？
答案也是no. 找到cycle后不能把visit[]置1！除非题目假设了graph里只有一个cycle，否则想象一下有一个点，从这个点出发，左边有一个cycle，右边有一个cycle，像∞这样，（或者上下各有个cycle，那就像8这样）。那么如果找到一个cycle后就把visit[]置1，那第二个cycle就没法被发现了。

  public List<List<Integer>> allCycles(Map<Integer, Set<Integer>> graph) {

    List<List<Integer>> result = new ArrayList<>();

    if (graph == null || graph.isEmpty()) {

      return result;

    }

 

    int[] visited = new int[graph.size()];

    for (int v : graph.keySet()) {

      if (visited[v] == 0) {

        List<Integer> tmp = new ArrayList<>();

        dfs(graph, v, visited, result, tmp);

      }

    }

    return result;

  }

 

  private void dfs(Map<Integer, Set<Integer>> graph, int v, int[] visited, List<List<Integer>> result, List<Integer> tmp) {

    if (visited[v] == -1) {

      List<Integer> cycle = new LinkedList<>();

      cycle.add(v);

      for (int i = tmp.size() - 1; i >= 0 ; i--) {

        cycle.add(0, tmp.get(i));

        if (tmp.get(i) == v) {

          break;

        }

      }

 

      result.add(new ArrayList<>(cycle));

      return;

    }

    if (visited[v] == 1) {

      return;

    }

 

    visited[v] = -1;

    tmp.add(v);

    for (int adj : graph.get(v)) {

      dfs(graph, adj, visited, result, tmp);

    }

    tmp.remove(tmp.size() - 1);

    visited[v] = 1;

  }

Read full article from Google – Print All Cycles in Graph