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.

how to print all paths in a directed graph

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

  1. 0 – 4 – 3
  2. 0 – 2 – 3
  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

https://www.quora.com/What-are-good-ways-to-find-all-the-possible-paths-between-two-nodes-in-a-directed-graph



Related Contents to follow