Нахождение всех возможных путей от данного начального узла до конечного узла

Question

Я пытаюсь распечатать все пути от источника до места назначения на графике, который использует список смежности. Он взвешен и направлен. Я пытаюсь сделать это в BFS. Спасибо за помощь. Я получаю только один путь. Как мне распечатать другие пути?

Вот функция BFS:

void BFS(struct Graph *G,QUEUE *q)
{
    int j,i=0;
    while(!isEmpty(q))
    {
        int source = dequeue(q);
        printf("%d ",source);
        path[i]=source;
        i++;
        if(source==bitis)//source==end
        {
            for(j=0;j<i;j++)
                printf("%d ",path[j]);
        }
        struct node *head = G->adjList[source]->next;
        while(head)
        {
            if(G->adjList[head->source]->marked)
            {
                head = head->next;
                continue;
            }
            G->adjList[head->source]->marked = 1;
            enqueue(head->source,q);
            head = G->adjList[head->source]->next;
        }
    }
}

Вот структура:

struct node{
    int source;
    int w;
    int marked;
    struct node *next;
};
struct Graph{
    int V;
    int E;
    struct node **adjList;
};

Здесь находится в списке:

[0]->[2]->[1]
[1]->[2]
[2]->[3]->[1]
[3]->[0]
[4]->[3]->[2]

Выход: 4 3 0

этот график:

1. 5 узлов, 9 ребер (A = 0, B = 1, C = 2, D = 3, E = 4)
2. начальный узел: 4 конечный узел: 0

этот график:

1. 5 узлов, 8 ребер (A = 0, B = 1, C = 2, D = 3, E = 4)
2. начальный узел: 4 конечный узел: 0

Я хочу, чтобы все пути между двумя значениями вводились пользователем. Если пользователь вводит 3 и 2

Я хочу, чтобы вывод был таким:

3 -> 0 -> 2
3 -> 0 -> 1 -> 2

Я надеюсь, что смогу выразить свой вопрос. Мой английский такой плохой. Спасибо.

Answer 1

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

Answer 2

Эта идея может быть полезна

create a queue which will store path(s) of type vector
initialise the queue with first path starting from src

Now run a loop till queue is not empty
   get the frontmost path from queue
   check if the lastnode of this path is destination
       if true then print the path
   run a loop for all the vertices connected to the
   current vertex i.e. lastnode extracted from path
      if the vertex is not visited in current path
         a) create a new path from earlier path and 
             append this vertex
         b) insert this new path to queue

Печать всех путей от данного источника к месту назначения с использованием BFS