Обнаружение всех кругов в графе

У меня есть ориентированный граф, хранящийся в структуре данных карты, где ключ - это идентификатор узла , а [значение] - это массив узловых узлов узлов, которые указываются ключевым узлом ,Обнаружение всех кругов в графе

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"});

Я написал алгоритм рекурсивного поиска, который пытается найти круг на графике.

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); 
    }

Функция вызывается кодом выше.

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); 
    } 
}

Некоторые пути содержат дополнительные узлы (которые не входят в круг), от которых я хотел бы избавиться. Хотелось бы обратиться за помощью, чтобы выбрать узлы из списков «путей», чтобы получить фактические узлы круга.

Может ли этот алгоритм найти ВСЕ круги на графике?

источник

2015-07-02 tyutyi

Вы можете объяснить немного больше о том, что вы подразумеваете под «кругом»? является ли ссылка на себя? возможно, вы можете добавить рис, чтобы объяснить, что вы имеете в виду, например. изображение с самого графика? –

Поскольку окружность в ориентированном графе представляет собой сильно связную компоненту, вы можете использовать любого из алгоритмов, упоминаемых на странице Википедии для поиска сильно связный компонента https://en.wikipedia.org/wiki/Strongly_connected_component - для алгоритма экземпляра Tarján, который основан на глубину первой категории: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

Редактирование: возможно, что сильно связанный компонент содержит несколько окружностей, которые обмениваются узлами друг с другом. Таким образом, ручная проверка каждого компонента должна выполняться, но должна быть простой.

источник

2015-07-13 20:48:24 DubioserKerl

Хотя все сильно связанные компоненты являются кругами, не все круги являются сильно связанными компонентами. – bhspencer

рассмотрите это изображение https://en.wikipedia.org/wiki/Strongly_connected_component#/media/File:Scc.png a-> b-> f-> e-> a - это круг, но не сильно связанный компонент – bhspencer

a -> b-> f-> e-> a не является окружностью - нет ребра от f до e. – DubioserKerl

Обнаружение всех кругов в графе

ответ

Смежные вопросы