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

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

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

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

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

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

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

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;

c++ recursion directed-graph
person ViscousRandom    schedule 07.12.2012    source источник
comment
Графики обычно хранятся в виде списков смежности или матрицы смежности. Ваш вклад в вопрос фактически является списком смежности.   -  person YXD    schedule 07.12.2012

Ответы (2)


arrow_upward
2
arrow_downward

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

        1    2    3    4

1   0    1    1    0

2   0    0    0    1

3   0    0    0    1

4   1    0    0    0

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

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

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

person bhuang3    schedule 07.12.2012

arrow_upward
1
arrow_downward

Вы также можете использовать Boost::Graph, если не хочется изобретать велосипед...

person DanDan    schedule 09.01.2013