Question

Language: Java or C (NO OTHER LANGUAGE)

Do NOT use Java library implementations of the data structures (queues, lists, STs, hashtables etc.)

Have a unit test implemented in main(). And comment every code.

Show examples from the executions.

Assume that the edges defined by the vertex pairs are two-way.

Question:
First step: write a program based on DFS which can answer questions of the type: "Find the a path from X to Y" Which should result in a list of vertices traversed from X to Y if there is a path.
Second step: Change the program to use BFS.

For the vertex pairs use this as your input:

AL FL
AL GA
AL MS
AL TN
AR LA
AR MO
AR MS
AR OK
AR TN
AR TX
AZ CA
AZ NM
AZ NV
AZ UT
CA NV
CA OR
CO KS
CO NE
CO NM
CO OK
CO UT
CO WY
CT MA
CT NY
CT RI
DC MD
DC VA
DE MD
DE NJ
DE PA
FL GA
GA NC
GA SC
GA TN
IA IL
IA MN
IA MO
IA NE
IA SD
IA WI
ID MT
ID NV
ID OR
ID UT
ID WA
ID WY
IL IN
IL KY
IL MO
IL WI
IN KY
IN MI
IN OH
KS MO
KS NE
KS OK
KY MO
KY OH
KY TN
KY VA
KY WV
LA MS
LA TX
MA NH
MA NY
MA RI
MA VT
MD PA
MD VA
MD WV
ME NH
MI OH
MI WI
MN ND
MN SD
MN WI
MO NE
MO OK
MO TN
MS TN
MT ND
MT SD
MT WY
NC SC
NC TN
NC VA
ND SD
NE SD
NE WY
NH VT
NJ NY
NJ PA
NM OK
NM TX
NV OR
NV UT
NY PA
NY VT
OH PA
OH WV
OK TX
OR WA
PA WV
SD WY
TN VA
UT WY
VA WV

Answer 1

Depth Fisrt Search(DFS)

​
#include<stdio.h>
#include<conio.h>
int a[20][20],reach[20],n;
void dfs(int v) 
{
        int i;
        reach[v]=1;
        for (i=1;i<=n;i++)
          if(a[v][i] && !reach[i]) 
{
                printf("\n %d->%d",v,i);
                dfs(i);
        }
}
void main() 
{
        int i,j,count=0;
        clrscr();
        printf("\n Enter number of vertices:");
        scanf("%d",&n);
        for (i=1;i<=n;i++) 
{
                reach[i]=0;
                for (j=1;j<=n;j++)
                   a[i][j]=0;
        }
        printf("\n Enter the adjacency matrix:\n");
        for (i=1;i<=n;i++)
          for (j=1;j<=n;j++)
           scanf("%d",&a[i][j]);
        dfs(1);
        printf("\n");
        for (i=1;i<=n;i++) 
{
                if(reach[i])
                   count++;
        }
        if(count==n)
          printf("\n Graph is connected"); else
          printf("\n Graph is not connected");
        getch();
}
​

Breadth First Search (BFS)

#include<stdio.h>
int a[20][20], q[20], visited[20], n, i, j, f = 0, r = -1;

void bfs(int v)
 {
        for(i = 1; i <= n; i++)
                if(a[v][i] && !visited[i])
                        q[++r] = i;
        if(f <= r)
 {
                visited[q[f]] = 1;
                bfs(q[f++]);
        }
}

void main()
 {
        int v;
        printf("\n Enter the number of vertices:");
        scanf("%d", &n);
        
        for(i=1; i <= n; i++) 
{
                q[i] = 0;
                visited[i] = 0;
        }
        
        printf("\n Enter graph data in matrix form:\n");
        for(i=1; i<=n; i++) 
{
                for(j=1;j<=n;j++) 
{
                        scanf("%d", &a[i][j]);
                }
        }
        
        printf("\n Enter the starting vertex:");
        scanf("%d", &v);
        bfs(v);
        printf("\n The node which are reachable are:\n");
        
        for(i=1; i <= n; i++) 
{
                if(visited[i])
                        printf("%d\t", i);
                else {
                        printf("\n Bfs is not possible. Not all nodes are reachable");
                        break;
                }
        }
}