检测图中的所有圆圈 [英] Detecting all circles in a graph

问题描述

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

 映射< String，String []> map = new HashMap< String，String []>（）; 
 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}）; 
  

我写了一个递归搜索算法，试图找出图中的圆。

 设置< String> nodes = map.keySet（）; 
 
 for（String node：nodes）{
 List< String> forbiddens = new ArrayList<>（）; //此过程中，此列表存储触摸的节点。 
 forbidden.add（node）; 
 recursiveSearch（node，forbiddens）; 
} 
  

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

  private void recursiveSearch（String nodeId，List< String> forbiddens）{
 String [] neighbors = map.get（nodeId）; //给定节点的邻居
 for（String neighbor：neighbors）{
 for（String forbidden：forbiddens）{
 if（neighbour.equals（forbidden））{
 ways。 add（getClone（forbidden））; // getClone返回给定列表的副本，ways是列表< List< String>>其中包含导致图中
返回的圆的路径列表; 
} 
} 
 forbidden.add（neighbor）; 
 recursiveSearch（neighbor，forbiddens）; 
 forbiddens.remove（邻居）; 
 
 
 
 
 
 
 $ b 
有些路径包含额外的节点（它们不在该圈子），我想摆脱。 
我想要求帮助从路径列表中选择节点来获得圆的实际节点。
 
 
这个算法能找到所有的图中的圆圈？
解决方案
由于有向图中的圆圈表示强连通的组件，因此您可以使用任何在wikipedia页面上引用的用于查找强连接组件的算法 https://en.wikipedia.org/wiki/Strongly_connected_component   - 例如基于深度优先搜索的Tarjan算法： https：// en。 wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm   
 
 
编辑：一个强连通的组件可能包含多个彼此共享节点的圆。因此，必须手动检查每个组件，但应该很容易。 
I have a directed graph stored in a Map data structure, where the key is the node's ID 
and the [value] is the array of the nodeIds of the nodes which are pointed by the key node.
Map<String, String[]> map = new HashMap<String, String[]>();
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"});
I wrote a recursive searching algorithm which tries to locate the circle in the graph.
Set<String> nodes = map.keySet();

    for(String node : nodes) {
        List<String> forbiddens = new ArrayList<>(); // This list stores the touched nodes, during the process.
        forbiddens.add(node);
        recursiveSearch(node, forbiddens);
    }
The function is called by the code above.
private void recursiveSearch(String nodeId, List<String> 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<String>> 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);
    }
}
Some paths contains extra nodes (which aren't in the circle) that I would like to get rid of.
I would like to ask for help to select the nodes from the "ways" lists to get the actual nodes of the circle.

Can this algorithm find ALL the circles in the graph?
解决方案
Since a circle in a directed graph represents a strongly connected component, you can use any of the algorithms referenced on the wikipedia page for finding strongly connected components https://en.wikipedia.org/wiki/Strongly_connected_component - for instance Tarjan's algorithm which is based on depth-first search: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

Edit: It is possible that a strongly connected component contains multiple circles that share nodes with each other. So, a manual checking of each component must follow, but should be easy.

                        
这篇关于检测图中的所有圆圈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！