in c++ You are to implement a straightforward application of Depth First Search

Question

in c++

You are to implement a straightforward application of Depth First Search (DFS): Find all reachable nodes from a given start node. Input The input should be read from the file graph.txt Use file redirection for this. The first line of the input contains only one token, n - the number of nodes of an undirected graph. Next, the boolean adjacency matrix is read in line by line, n lines in total The program should check that all diagonal elements are 0 (i.e. false) and that the matrix is symmetric; print an error message if this is not the case The last line of the input is only one token, the chosen start node s sum {1, ....., n} Method Use DFS starting at node s. Output Print out the nodes reachable from s, including s.

Explanation / Answer

#include <iostream>
#include <list>
#include <fstream>
using namespace std;

int a[20][20], visited[20], n, i, j;

void dfs(int v)
{
int j;
visited[v]=1;

for(j=1; j<=n; j++)
if(!visited[j]&&a[v][j])
dfs(j);
}

int main()
{
int v;
FILE *file = fopen("data.txt","r");

fscanf(file, "%d" , &n);

// Read the data into the matrix
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
{
fscanf(file, " %d", &a[i][j] );
}
}

for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
{
if(a[i][i] != 0)
{
cout << "The diagonal elements of the matrix are not 0" << endl;
return 0;
}

else if(!(a[j][i]==a[i][j]&& i==j))
{
cout << "The given matrix is not Symmetric Matrix "<<endl;
return 0;
}

}
}

fscanf(file, "%d" , &v);
dfs(v);

cout << "The nodes which are reachable are from " << v << " : ";
for(i=1; i<=n; i++)
{
if(visited[i])
cout << i << endl;
}
return 0;
}

data.txt

5
0 1 0 1 0
0 0 0 1 1
1 0 0 1 0
0 0 0 0 1
0 0 0 0 0
1

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.