Алгоритм графика для нахождения всех соединений между двумя произвольными вершинами
7 ответов
Кажется, что это может быть выполнено с поиском в глубину графика. поиск в глубину найдет все нециклические пути между двумя узлами. Этот алгоритм должен быть очень быстрым и масштабироваться к большим графикам (Структура данных графика редка, таким образом, это только использует столько памяти, сколько этому нужно к).
я заметил, что график, который Вы определили выше, имеет только один край, который направлен (B, E). Действительно ли это было опечаткой, или это - действительно ориентированный граф? Это решение работает независимо. Извините я был неспособен сделать это в C, я немного слаб в той области. Я ожидаю, что Вы будете в состоянии перевести этот код Java без слишком большой проблемы все же.
Graph.java:
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;
public class Graph {
private Map<String, LinkedHashSet<String>> map = new HashMap();
public void addEdge(String node1, String node2) {
LinkedHashSet<String> adjacent = map.get(node1);
if(adjacent==null) {
adjacent = new LinkedHashSet();
map.put(node1, adjacent);
}
adjacent.add(node2);
}
public void addTwoWayVertex(String node1, String node2) {
addEdge(node1, node2);
addEdge(node2, node1);
}
public boolean isConnected(String node1, String node2) {
Set adjacent = map.get(node1);
if(adjacent==null) {
return false;
}
return adjacent.contains(node2);
}
public LinkedList<String> adjacentNodes(String last) {
LinkedHashSet<String> adjacent = map.get(last);
if(adjacent==null) {
return new LinkedList();
}
return new LinkedList<String>(adjacent);
}
}
Search.java:
import java.util.LinkedList;
public class Search {
private static final String START = "B";
private static final String END = "E";
public static void main(String[] args) {
// this graph is directional
Graph graph = new Graph();
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "A");
graph.addEdge("B", "D");
graph.addEdge("B", "E"); // this is the only one-way connection
graph.addEdge("B", "F");
graph.addEdge("C", "A");
graph.addEdge("C", "E");
graph.addEdge("C", "F");
graph.addEdge("D", "B");
graph.addEdge("E", "C");
graph.addEdge("E", "F");
graph.addEdge("F", "B");
graph.addEdge("F", "C");
graph.addEdge("F", "E");
LinkedList<String> visited = new LinkedList();
visited.add(START);
new Search().depthFirst(graph, visited);
}
private void depthFirst(Graph graph, LinkedList<String> visited) {
LinkedList<String> nodes = graph.adjacentNodes(visited.getLast());
// examine adjacent nodes
for (String node : nodes) {
if (visited.contains(node)) {
continue;
}
if (node.equals(END)) {
visited.add(node);
printPath(visited);
visited.removeLast();
break;
}
}
for (String node : nodes) {
if (visited.contains(node) || node.equals(END)) {
continue;
}
visited.addLast(node);
depthFirst(graph, visited);
visited.removeLast();
}
}
private void printPath(LinkedList<String> visited) {
for (String node : visited) {
System.out.print(node);
System.out.print(" ");
}
System.out.println();
}
}
Вывод Программы:
B E
B A C E
B A C F E
B F E
B F C E
Насколько я могу сказать решения, данные Ryan Fox ( 58343 , христианин ( 58444 ), и Вы ( 58461 ) почти так же хороши, как это добирается. Я не полагаю, что обход в ширину помогает в этом случае, поскольку Вы не получите все пути. Например, с краями (A,B), (A,C), (B,C), (B,D) и (C,D) Вы получите пути ABD и ACD, но не ABCD.
Вот мысль первое, что пришло на ум:
- Находят одно соединение. (Поиск в глубину является, вероятно, хорошим алгоритмом для этого, так как длина пути не имеет значения.)
- Отключают последний сегмент.
- Попытка найти другое соединение от последнего узла перед ранее отключенным соединением.
- Goto 2 до больше нет соединений.
Я решил подобную проблему к этому недавно вместо всех решений, я только интересовался самым коротким.
я использовал повторяющийся поиск 'в ширину', который использовал очередь состояния, каждый из которых содержал запись, содержащую текущую точку на графике и пути, взятом для получения там.
Вы запускаете с единственной записи в очереди, которая имеет стартовый узел и пустой путь.
Каждое повторение через код берет объект от заголовка списка и проверки, чтобы видеть, является ли это решение (узел прибыл в, тот, который Вы хотите, если это, мы сделаны), иначе, это создает новый объект очереди с узлами, соединяющимися с текущим узлом и исправленными путями, которые основаны на пути предыдущего узла с новым переходом, присоединенным в конце.
Теперь, Вы могли использовать что-то подобное, но когда Вы находите, что решение, вместо остановки, добавляет, что решение Вашего 'найденного списка' и продолжается.
необходимо отслеживать посещаемый список узлов, так, чтобы Вы никогда не отслеживали в обратном порядке на себе иначе, у Вас есть бесконечный цикл.
, если Вы хотите немного больше псевдокода, добавляют комментарий или что-то, и я уточню.
Вот псевдокод, который я придумал. Это не конкретный диалект псевдокода, но должно быть достаточно просто следовать.
Любой хочет выбрать это независимо.
-
[p] список вершин, представляющих текущий путь.
-
[x] список путей, где соответствуют критериям
-
[s], исходная вершина
-
[d], целевая вершина
-
[c], текущая вершина (аргумент стандартной программе PathFind)
Предполагают, что существует эффективный способ искать смежные вершины (строка 6).
1 PathList [p]
2 ListOfPathLists [x]
3 Vertex [s], [d]
4 PathFind ( Vertex [c] )
5 Add [c] to tail end of list [p]
6 For each Vertex [v] adjacent to [c]
7 If [v] is equal to [d] then
8 Save list [p] in [x]
9 Else If [v] is not in list [p]
10 PathFind([v])
11 Next For
12 Remove tail from [p]
13 Return
Национальный институт стандартов и технологий (NIST) онлайновый словарь Алгоритмов и Структур данных перечисляет эту проблему как" все простые контуры" и рекомендует поиск в глубину . СБРАСЫВАЕТ предоставляет соответствующие алгоритмы.
А умная техника с помощью сетей Петри найдена здесь
Я думаю, что необходимо описать настоящую проблему позади этого. Я говорю это, потому что Вы просите что-то у эффективного времени, все же набор ответа к проблеме, кажется, растет экспоненциально!
Поэтому я не ожидал бы лучший алгоритм, чем что-то экспоненциальное.
я сделал бы отслеживание в обратном порядке и прохождение через целого графика. Для предотвращения циклов сохраните все посещаемые узлы по пути. Когда Вы возвращаетесь, снимаете выделение с узла.
Используя рекурсию:
static bool[] visited;//all false
Stack<int> currentway; initialize empty
function findnodes(int nextnode)
{
if (nextnode==destnode)
{
print currentway
return;
}
visited[nextnode]=true;
Push nextnode to the end of currentway.
for each node n accesible from nextnode:
findnodes(n);
visited[nextnode]=false;
pop from currenteay
}
Или та несправедливость?
редактирование: О, и я забыл: необходимо устранить рекурсивные вызовы путем использования той стопки узла