检测图表中的所有圆圈

我有一个存储在Map数据结构中的有向图，其中键是节点的ID，[value]是由关键节点指向的节点的nodeIds的数组。

Map map = new HashMap(); map.put("1", new String[] {"2", "5"}); map.put("2", new String[] {"3"}); map.put("3", new String[] {"4"}); map.put("4", new String[] {"4"}); map.put("5", new String[] {"5", "9"}); map.put("6", new String[] {"5"}); map.put("7", new String[] {"6"}); map.put("8", new String[] {"6"}); map.put("9", new String[] {"10"}); map.put("10", new String[] {"5"}); map.put("11", new String[] {"11"}); 

我写了一个递归搜索算法，试图在图中找到圆圈。

 Set nodes = map.keySet(); for(String node : nodes) { List forbiddens = new ArrayList(); // This list stores the touched nodes, during the process. forbiddens.add(node); recursiveSearch(node, forbiddens); } 

该函数由上面的代码调用。

 private void recursiveSearch(String nodeId, List forbiddens) { String[] neighbours = map.get(nodeId); // The given node's neighbours for(String neighbour : neighbours) { for(String forbidden : forbiddens) { if(neighbour.equals(forbidden)) { ways.add( getClone(forbidden) ); //getClone returns the copy of a given List, "ways" is a List<List> which contains the lists of paths which are leading to a circle in the graph return; } } forbiddens.add(neighbour); recursiveSearch(neighbour, forbiddens); forbiddens.remove(neighbour); } } 

有些路径包含我想要删除的额外节点（不在圆圈中）。 我想请求帮助从“方式”列表中选择节点以获取圆的实际节点。

这个算法可以找到图中的所有圆圈吗？

Answer 1

由于有向图中的圆圈表示强连接组件，因此您可以使用维基百科页面上引用的任何算法来查找强连接组件https://en.wikipedia.org/wiki/Strongly_connected_component – 例如Tarjan的算法，即基于深度优先搜索： https ： //en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

编辑：强连接组件可能包含多个彼此共享节点的圆圈。 因此，必须手动检查每个组件，但应该很容易。