I need to use Depth first search and breadth first search to traverse a maze gra
ID: 2902774 • Letter: I
Question
I need to use Depth first search and breadth first search to traverse a maze graph that is imported from a .txt file. Im not sure how to do the external file manipulation to get it in to the code that I have done. I am coding in C++.
The graph looks like this :
XXXXXXX
XS X
XXX X
X X X
X X X
X X GX
XXXXXXX
I have the following code:
#include<iostream>
#define MAX 10
using namespace std;
class DFS
{
private : int n;
int adj[MAX][MAX];
int visited[MAX];
public : void dfs(int);
void readmatrix();
};
void DFS :: readmatrix()
{
int i,j;
cout << " Enter the number of Vertices in the Graph : ";
cin >> n;
cout << " Enter the Adjacency Matrix ";
for (i = 1; i <= n; i++)
for (j = 1; j<= n; j++)
cin >> adj[i][j];
for (i = 1; i <= n; i++)
visited[i] = 0;
}
void DFS :: dfs(int source)
{
int i;
visited[source] = 1;
cout << source << " ";
for (i = 1; i <= n; i++)
if (adj[source][i] && !visited[i])
dfs(i);
}
class BFS
{
private : int n;
int adj[MAX][MAX];
int visited[MAX];
public : void bfs(int);
void readmatrix();
};
void BFS :: readmatrix()
{
int i,j;
cout << " Enter the number of Vertices in the Graph : ";
cin >> n;
cout << " Enter the Adjacency Matrix ";
for (i = 1; i <= n; i++)
for (j = 1; j<= n; j++)
cin >> adj[i][j];
for (i = 1; i <= n; i++)
visited[i] = 0;
}
void BFS :: bfs(int source)
{
int queue[MAX];
int i, front, rear, root;
front = rear = 0;
visited[source] = 1;
queue[rear++] = source;
cout << source << " ";
while (front != rear)
{
root = queue[front];
for (i = 1; i <= n; i++)
if (adj[root][i] && !visited[i])
{
visited[i] = 1;
queue[rear++] = i;
cout << i << " ";
}
front++;
}
}
int main()
{
int source;
DFS depth;
BFS breadth;
depth.readmatrix();
breadth.readmatrix();
cout << " Enter the Source : ";
cin >> source;
cout << " The nodes visited in the DFS order is : ";
depth.dfs(source);
breadth.bfs(source);
return 0;
}
Explanation / Answer
#include <fstream>
using namespace std;
ifstream inFile;
inFile.open(".txt");
if (!inFile) {
cerr << "Unable to open file datafile.txt";
exit(1); // call system to stop
}
while (inFile >> x)
{
sum = sum + x;
}
inFile.close();
#include <iostream>
#include <iomanip>
#include <fstream>
using namespace std;
int main() {
int sum = 0;
int x;
ifstream inFile;
inFile.open("test.txt");
if (!inFile) {
cout << "Unable to open file";
exit(1); // terminate with error
}
while (inFile >> x) {
sum = sum + x;
}
inFile.close();
cout << "Sum = " << sum << endl;
return 0;
}
*/
#include<iostream>
#define MAX 10
using namespace std;
class DFS
{
private : int n;
int adj[MAX][MAX];
int visited[MAX];
public : void dfs(int);
void readmatrix();
};
void DFS :: readmatrix()
{
int i,j;
cout << " Enter the number of Vertices in the Graph : ";
cin >> n;
cout << " Enter the Adjacency Matrix ";
for (i = 1; i <= n; i++)
for (j = 1; j<= n; j++)
cin >> adj[i][j];
for (i = 1; i <= n; i++)
visited[i] = 0;
}
void DFS :: dfs(int source)
{
int i;
visited[source] = 1;
cout << source << " ";
for (i = 1; i <= n; i++)
if (adj[source][i] && !visited[i])
dfs(i);
}
class BFS
{
private : int n;
int adj[MAX][MAX];
int visited[MAX];
public : void bfs(int);
void readmatrix();
};
void BFS :: readmatrix()
{
int i,j;
cout << " Enter the number of Vertices in the Graph : ";
cin >> n;
cout << " Enter the Adjacency Matrix ";
for (i = 1; i <= n; i++)
for (j = 1; j<= n; j++)
cin >> adj[i][j];
for (i = 1; i <= n; i++)
visited[i] = 0;
}
void BFS :: bfs(int source)
{
int queue[MAX];
int i, front, rear, root;
front = rear = 0;
visited[source] = 1;
queue[rear++] = source;
cout << source << " ";
while (front != rear)
{
root = queue[front];
for (i = 1; i <= n; i++)
if (adj[root][i] && !visited[i])
{
visited[i] = 1;
queue[rear++] = i;
cout << i << " ";
}
front++;
}
}
int main()
{
int source;
DFS depth;
BFS breadth;
depth.readmatrix();
breadth.readmatrix();
cout << " Enter the Source : ";
cin >> source;
cout << " The nodes visited in the DFS order is : ";
depth.dfs(source);
breadth.bfs(source);
return 0;
}