Question

IN C++
Write a BFS path or DFS when it is given a string array of vertices "towns":
string towns[]={"Seattle","Lynnwood","Edmonds","Shoreline","Everet","Kenmore","Kirkland"};
and int array of edges:
int roads [][2]=
{0,1},{0,3},
{1,0},{1,5},
  {2,4},
{3,0},{3,5},
  {4,2},
{5,1},{5,3},{5,6},
  {6,5};

Do not create any graph struct,class or egde struct. You only need to create a BFS or DFS path function that
accepts parameters the array of strings, the number of verteces,the array of edges and the nuber of edges.

for example you call in main the function:
pathBfs(towns,7,roads,12);

Please need help.

Answer 1

#include <iostream>
#include <map>
using namespace std;

map < int, bool > used;

void DFS(string towns[7], int roads[12][2], int numberOfEdges, int v) {
cout << towns[v] << "; ";
for (int i = 0; i < numberOfEdges; i++) {
if (roads[i][0] == v) {
if (!used[roads[i][1]]) {
used[roads[i][1]] = 1;
DFS(towns, roads, numberOfEdges, roads[i][1]);
}
} else if (roads[i][1] == v) {
if (!used[roads[i][0]]) {
used[roads[i][0]] = 1;
DFS(towns, roads, numberOfEdges, roads[i][0]);
}
}
}
}

void pathDFS(string towns[7], int roads[12][2], int numberOfEdges) {
int startingPoint = 0;
used[startingPoint] = 1;
DFS(towns, roads, 12, startingPoint);
}

int main()
{
string towns[]={"Seattle","Lynnwood","Edmonds","Shoreline","Everet","Kenmore","Kirkland"};
int roads [][2]= {{0,1},{0,3},{1,0},{1,5},{2,4},{3,0},{3,5},{4,2},{5,1},{5,3},{5,6},{6,5}};
pathDFS(towns, roads, 7);
return 0;
}

pathDFS is a function which calls actual recursion function(DFS). Used map is required to determine if we were in the vertex, otherwise time limit will be crossed and DFS will never stop.

comment down for any queries

please give a thumbs up