In: Computer Science
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.
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
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;
}
}
}