Обнаружение всех кругов на графике
У меня есть направленный граф, хранящийся в структуре данных Map, где ключ - это идентификатор узла, а [значение] - это массив идентификаторов узлов, которые указываются ключевым узлом.
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);
}
}
Некоторые пути содержат дополнительные узлы (которых нет в круге), от которых я хотел бы избавиться. Я хотел бы попросить помощи, чтобы выбрать узлы из списков "путей", чтобы получить фактические узлы круга.
Может ли этот алгоритм найти ВСЕ круги на графике?