A volvo bus driver needs to enroute the
bus within n cities by connecting all cities in a cyclic pattern. As the
business analyst write a program to check if he is able to visit all the cities
in a cyclic path for the given paths.
Input:
Input consists of an integer denoting the
number of cities n. Using 'n' a 2D array boolean graph[n][n] is formed where n
is the number of vertices (cities) in graph. The integer 'n' is followed by
space separated graph values where graph[i][j] = 1 represents that there is a
direct path from i to j, otherwise graph[i][j] = 0.
Output:
An array path[V] that should contain the
path in the graph such that it visits each vertex exactly once. If a path
exists, then print the path starting from 0. The code should also return false
if there is no such cyclic path in the graph.
Sample:
1] Input: 4 0 1 1 0 1 0 0 0 0 0 0 1 0 1 1
0
Output: 0 2 3 1 0
2] Input: 3 0 1 1 1 0 0 1 0 0
Output: -1
Solution:
#include<stdio.h>
#include<stdbool.h>
int V;
void printSolution(int path[]);
bool isSafe(int v, bool graph[V][V], int
path[], int pos)
{
int i;
if (graph [ path[pos-1] ][ v ] == 0)
return false;
for (i = 0; i < pos; i++)
if (path[i] == v)
return false;
return true;
}
bool hamCycleUtil(bool graph[V][V], int
path[], int pos)
{
int v;
if (pos == V)
{
if ( graph[ path[pos-1] ][ path[0] ] == 1 )
return true;
else
return false;
}
for (v = 1; v < V; v++)
{
if (isSafe(v, graph, path, pos))
{
path[pos] = v;
if (hamCycleUtil (graph, path, pos+1) == true)
return true;
path[pos] = -1;
}
}
return false;
}
bool hamCycle(bool graph[V][V])
{
int *path = malloc(V);
int i;
for (i = 0; i < V; i++)
path[i] = -1;
path[0] = 0;
if ( hamCycleUtil(graph, path, 1) == false )
{
printf("-1");
return false;
}
printSolution(path);
return true;
}
void printSolution(int path[])
{
int i;
for (i = 0; i < V; i++)
printf("%d ", path[i]);
printf("%d ", path[0]);
printf("\n");
}
int main(int argc, char *argv[])
{
V
= atoi(argv[1]);
bool graph[V][V];
int i, j, x=2;
for(i=0;i<V;i++)
for(j=0;j<V;j++){
graph[i][j] = atoi(argv[x]);
x++;
}
hamCycle(graph);
return 0;
}