C path of programming adjacency matrices
How do I know if a path exists from index1 to index2 in a given adjacency matrix?
Do I need to use recursion?
This is my code:
int path(int adj_mat[][N], int*pindex1, int *pindex2)
{
int i=0; //column
int yes=0; //flag
int j;
for(i;i<N;i++)
{
if(adj_mat[i][*pindex2-1]==1)
{
if(i==*pindex1-1)
yes=1;
for(j=i-1; j<0;--j)
{
if(adj_mat[j][i]==1)
if(j==*pindex1-1)
yes=1;
}
}
}
return yes;
}
source to share
I think your adjacency matrix of received values 0
and 1
as values. In your case, 0
means there is no path between index1
and index2
and 1
means that it exists.
so for a given matrix:
0 | 0 | 0
-----------
0 | 1 | 0
-----------
0 | 0 | 0
there is only one path from index1 = 1
to index2 = 1
:
matrix[1][1] = 1 => a path exists
matrix[0][1] = 0 => a path does not exist
So, you just need to return the content and check it ...:
return adj_mat[*pindex1][*pindex2];
source to share