# how to print all paths in a directed graph

“*how to print all paths in a directed graph”* is famous question asked in programming interview. Given a directed graph write a c program to find all paths between two given nodes of a directed graph. For example what are the paths between vertex 0 to vertex 3.

The paths from source node or vertex 0 to destination node or vertex 3 are

**0 – 4 – 3****0 – 2 – 3****0 – 4 – 2 – 3**

*Learn how to print all paths in a directed graph step by step*

* Represent the above graph as adjacency matrix ( Read more at http://wikistack.com/graph-and-its-representationtutorial/ )
*

#include<stdio.h> #define N 5 int graph[N][N] = { {0,1,1,0,1}, {0,0,0,0,0}, {0,1,0,1,0}, {0,0,0,0,0}, {0,0,1,1,0},};

After representing the graph as adjacency matrix we run DFS like recursive function from the source node. Here is c implementation.

#include<stdio.h> #include<string.h> #define N 5 #define true 1 #define false 0 int graph[N][N] = { {0, 1, 1, 0, 1}, {0, 0, 0, 0, 0}, {0, 1, 0, 1, 0}, {0, 0, 0, 0, 0}, {0, 0, 1, 1, 0}, }; int path[N]; int visited[N]; int indx = 0; void printPath (int src, int dest); void print_stack_elements (); int main () { // set all nodes unvisited memset (visited, 0, sizeof (visited)); printPath (0, 3); return 0; } void printPath (int src, int dest) { visited[src] = true; path[indx] = src; indx++; if (src == dest) { print_stack_elements (); } else { int i; for (i = 0; i < N; i++) { if (visited[i] == false && graph[src][i]) printPath (i, dest); } } visited[src] = false; indx--; } void print_stack_elements () { int i; for (i = 0; i < indx; i++) printf ("%d ", path[i]); printf ("\n"); }

Ref:

http://stackoverflow.com/questions/9535819/find-all-paths-between-two-graph-nodes

## Leave a Reply