Java-код для создания путей

Question

Попытка ввести код в java. Пожалуйста, предложите любой алгоритм, который будет работать для этого сценария. вход является:

Col A Col B 
A  B 
A  C 
B  D 
C  A 
C  B 
C  E 
D  A 
D  B 
E  A 

Я пытаюсь сделать комбинации, такие как выход:

A B D A  
A C A   
A C B D A 
A C E A  
B D B   
C A B D A C 
C A C   
C B D A C 
C E A C 

| 
| 
| 

и так далее. Выход должен иметь начальную точку и конечную точку как то же самое.

Другой способ взглянуть на это, вы начинаете с узла A, и вам нужно вернуться к узлу A, поэтому ваш путь будет от A до B, а от B до D (потому что из B вы можете идти к одному узлу, то есть D), затем от D до A. Итак, col A и Col B дают вам возможные пути, например, из A вы можете перейти только в B и C, а не D и E. Надеюсь, это поможет. Кроме того, есть ли способ ограничить число. узлов для решения?

Пожалуйста, предложите несколько идей.

Answer 1

Вы должны использовать рекурсию, и как вы рекурсию через данные необходимо отметить, где вы побывали, так что вы не идти по тому же пути бесконечно,

Answer 2

Из данных, у вас есть коллекция из пяти отдельные узлы - A, B, C, D и E.

Если соединить их вместе, то получим отображение того, что относится к чему:

A: [B, C] 
B: [D] 
C: [B, E] 
D: [A, B] 
E: [A] 

выше представляет собой sparse graph. Узел не соединяется непосредственно с собой из другого узла, кроме B-> D-> B.

Вот процесс потока, как я подхожу к нему.

• Используйте Map<String, List<String> для первичного узла я достичь, а ребра, что этот узел соединен с.

• Выберите начальный узел, a. Поместите свои ссылки в стек.

• Проверьте, совпадает ли конечный узел с началом.
  • Если это так, вы закончили - вытащите элементы из стека и получите свой путь.
  • Если это не так, вытащите первый элемент из стека и нажмите его ссылки в стек. Повторите проверку.
• Если нет ничего совать, то нет никакого пути от к .

Этот стиль обхода - depth first search. Вы углубляетесь в график, пока не достигнете своего пути или не исчерпаете свои возможности.