Path in a directed graph

Write an algorithm to find if a path exists between two nodes in a directed graph.


1 ————> 2 ————> 3
↑ |
| |
| ↓
4 ————> 5 ————> 6


Answer:


#include "stdio.h"
#include "stdlib.h"
#include "assert.h"

#define IS_CONNECTED(from,to) graph[(from-1)][(to-1)]

int graph[6][6]= {
{0, 1, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 1, 0},
{0, 1, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0}
};

bool isReachable(size_t from, size_t to)
{
const int n = 6;
printf("\n isReachable %d -> %d \n", from, to );
if ( from == to )
return true;
if(IS_CONNECTED(from, to))
return true;
else
{
for( size_t i =1; i <= n; ++i )
{
if( IS_CONNECTED(i,to) )
{
if (isReachable( from, i))
return true;
continue;
}
}
return false;
}
}

int main(int argc, char* argv[])
{
size_t from = atoi(argv[1]);
size_t to = atoi(argv[2]);
assert( (from <= 6) && (from >=1) );
assert( (to <= 6) && (to >=1) );
return printf("\n Is Reachable(%d -> %d) %d\n", from, to, isReachable(from, to ));
}

No comments: