0

So I have a graph in the form of an adjacency list, structured as in the code below. Given this form of a data structure, I was wondering how it would be possible to go about finding and printing all the possible paths from a given node to another node. I'm aware I might have to used stacks to perform a DFS or queues to perform BFS, which I know how to do, but am confused by how to find all the possible paths 

typedef struct graph {
    int n, maxn;
    Vertex** vertices;
}Graph;

typedef struct vertex {
    char* label;
    Edge* first_edge;
}Vertex;

typedef struct edge {
    int u, v;
    int weight;
    Edge* next_edge;
}Edge ;
Harambe
  • 3
  • 2
  • I think there is basically no other way than using BFS or DFS. – Codor Mar 31 '17 at 14:13
  • Yeah but would you happen to know how I could use them to find each and every possible path? – Harambe Mar 31 '17 at 14:16
  • if you don't know how to use stacks, why not use a recursive method instead? – Chris Turner Mar 31 '17 at 14:17
  • https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm – Sinan Ünür Mar 31 '17 at 14:18
  • If you use DFS, do not mark the nodes as visited (or un-mark them when returning from recursive calls). Maintain a stack of currently visited nodes and make sure that you do not visit a node which is currently contained in the stack (or marked). Whenever you reach the destination node, the stack contains a new path from the start to the destination, which can be copied to the output. Note that the number of paths between two nodes may grow exponentially in the number of nodes of the graph. – Codor Mar 31 '17 at 14:20
  • 2
    Possible duplicate of [Find all paths between two graph nodes](http://stackoverflow.com/questions/9535819/find-all-paths-between-two-graph-nodes) – amit Mar 31 '17 at 14:27
  • Possible duplicate of http://stackoverflow.com/questions/43141511/best-way-to-implement-shortest-path-algorithm-with-directed-graph – Codor Mar 31 '17 at 14:32

0 Answers0