Implement the the DFS algorithm. Use a text file (called input.txt) that contain
ID: 3741228 • Letter: I
Question
Implement the the DFS algorithm. Use a text file (called input.txt) that contains an adjacency
matrix to read-in data and create a directed graph to be searched. The matrix can be of any size. Row
elements in the input.txt file must be separated with commas. Example:
1,0,1,0,1,1
0,0,1,1,0,1
:
0,0,1,1,0,1
The output of your program should provide the order of visited nodes. In addition to source and
documentation, provide a text file, called REPORT.TXT, briefly describing how (i.e. data structures) and
what you have implemented (i.e. what works, what doesn’t).
Tip: Follow the suggested DFS data structure for the algorithm. Don’t improvise.
Explanation / Answer
In the below DFS.c program i took a 4 node tree so if you want to take a bigger tree you can replace a value 4 in the code with the number of nodes you want.
#include <stdio.h> //library function
#define FOUR 4
void DFS1(int); //DFS function which calculates a depth first search nodes
int visited[20]; //This is array which will be used to monitor the visited nodes
int DFS[FOUR][FOUR]; //This is a two dimensional array which is used to store text file values
int main()
{
int i=0;
FILE *fp; //File pointer
fp = fopen("REPORTS.txt","r"); //we use fopen function to open the file REPORTS.txt
while((fscanf(fp,"%d,%d,%d,%d", &DFS[i][0],&DFS[i][1],&DFS[i][2],&DFS[i][3])) != EOF){ //A while looop which reads all values
//printf("%d %d %d %d ", DFS[i][0],DFS[i][1],DFS[i][2],DFS[i][3]);
i++;
}
for(i=0;i<FOUR;i++)
visited[i]=0; //initailizes all the values of visited array to 0
DFS1(0); //call th DFS1 function with a value 0
}
void DFS1(int i)
{
int j;
printf(" %d",i); //Here the actual printing of values with DFS
visited[i]=1;
for(j=0;j<FOUR;j++)
if(!visited[j]&&DFS[i][j]==1) // Here it will check for the nodes which are not visited previously and adjacent to node i
DFS1(j); //If found recursively calls the DFS1 function
}
REPORTS.txt
1,0,0,1
0,1,1,1
0,0,0,0
0,1,0,0
Output :
deepak@deepak-ThinkPad-SL:~$ gcc DFS.c
deepak@deepak-ThinkPad-SL:~$ ./a.out
0 3 1 2deepak@deepak-ThinkPad-SL:~$