Идея о том, как подойти к ориентированному графу

Question

Идея о том, как подойти к ориентированному графу

Я пытаюсь написать программу, использующую ориентированный граф (о котором я знаю, но никогда не реализовывал) для имитации сети транспортировки.

Пользователь введет имя планеты, за которым следует целое число, представляющее количество всех узлов на графике. Затем пользователь будет проходить через каждый узел один за другим. Они дадут ему имя, число соседей, которое имеет этот узел, а затем конкретные имена. Вход будет выглядеть следующим образом.

some_planet 4
node1 2 node2 node3
node2 1 node4
node3 1 node4
node4 1 node1

Затем я просто выводлю, какие узлы node1 не могут достичь. Однако у меня есть несколько вопросов по поводу реализации этого.

1) Большой хранит этот материал. Что такое легкий путь? Я думал о LinkedList и думал, что свяжу места. Тогда я мог бы добавить на них указатели, соответствующие любому входу. Тем не менее, я понятия не имею, как сделать последнюю часть.

2) Следующий большой поиск в графе. Я планировал рекурсивный поиск в глубину. Что-то не так с этим алгоритмом, который вы видите? Мне нужно искать каждый узел в отдельности таким образом, поэтому мне придется увеличивать это. Могу ли я просто бросить все в цикл?

recursive-d-first-search(graph G, node start, node find)
if(start == find)
return true;

else
for every neighbor n of start
success = recursive-d-first-search(graph G, node n, node find);
if(success)
return true;

return false;

2

c++directed-graph recursion

Решение

Другие решения

Вы также можете использовать Повысьте :: Graph если вы не хотите изобретать велосипед …

1

Источник

Accepted Answer

Я думаю, что вам просто нужно использовать матрицу смежности для хранения отношения соединения всего графа.
в вашем случае это должно выглядеть так:
```
    1    2    3    4

1   0    1    1    0

2   0    0    0    1

3   0    0    0    1

4   1    0    0    0
```
Если вы используете матрицу смежности, я думаю, breadth-first search может быть хорошим выбором, потому что это легко понять и реализовать. Между тем вам нужна одна очередь для хранения следующих проверяемых узлов и один список для хранения уже проверенных узлов

Например, вы хотите проверить, какие узлы node1 не может достичь, вы просто проверьте строку 1 и увидите, что он имеет 2 а также 3, и положи 2 а также 3 стоять в очереди. Затем проверьте строку 2 чтобы увидеть, что это имеет 4, положил 2 перечислить и положить 4 стоять в очереди. Затем просто используйте цикл for для выполнения той же операции.

В конце вам просто нужно проверить, какие узлы отсутствуют в списке.

2