Вывод кратчайшего пути из невзвешенного графа

#c #algorithm #graph #breadth-first-search

#c #алгоритм #График #поиск по ширине

Вопрос:

У меня есть ориентированный граф, представленный в виде списка смежности :

 class Graph
{
    private:
        struct Node
        {
            Node *next;
            int vertex;
            Node( int vertex )
            {
                this -> vertex = vertex;
                this -> next = nullptr;
            }
        };

        Node ** graph;
        int V;

public:
    Graph(int size)
    {
        V = size;
        graph = new Node*[V];
        for ( int i = 0; i < V; i   )
            graph[i] = nullptr;
    }

   // Add edge from Source to destination
   void addEdge( int source, int destination )  
   {
      Node * ref = graph[from];
      graph[from] = new Node( to );
      graph[from] -> next = ref;
   }

  void bfs ( int s, int dest )
  {
   // ...
  }

Я реализовал bfs, который дает мне кратчайший путь от узла A к узлу B, но я не знаю, как эффективно сохранить этот путь, а затем распечатать его. Есть идеи, как это решить?

1. почему бы вам не показать нам, как вы реализовали bfs, и вам будет легче разобраться, как сохранить ваши результаты.

2. @xaxxon обновил bfs

3. Я рекомендую создать карту «came from», в которой хранится, как вы добрались до каждого узла. Затем просто используйте эту карту, чтобы вернуться назад, когда достигнете своей цели.

Ответ №1:

Если вы выполняете BFS, начиная с узла A, все посещаемые вами узлы могут иметь несколько дочерних элементов, но у каждого есть только один родитель. При просмотре графика просто сохраните родительский элемент каждого посещаемого вами узла (который еще не был посещен).

Когда вы найдете узел B, просто найдите его родительский элемент, а затем родительский элемент его родителя и так далее. Это дает вам путь.

1. addEdge(0, 1) , addEdge(0, 2); это означает, что 0 является источником и родителем как 1, так и 2, поэтому graph[0] является указателем на связанный список из 2 узлов с именами 0 и 1. как мне сохранить указатель на родительский элемент, когда родительский элемент фактически не создан, это простоуказатель

2. @paxie Вы посетили массив, вы можете добавить еще один, содержащий родительский. Родительский элемент здесь означает узел, с которого вы посетили узел, поэтому в основном он должен быть visited[*i] = true; parent[*i]=s;

3. Используйте другую структуру данных для хранения родительского отношения. Массив a , например, где a[1] = 0 , а a[2]=0 затем вы можете просто перейти через массив.