Question

in c++ please

Suppose you have a non-weighted graph (just O's and 1's) with 8 vertices stored in the usual 2D array: graph[8][8]. You need to write a function that will traverse the graph in the following way: 1. The function is passed a starting vertex and a goal vertex (for simplicity, assume the size is 8 since the graph array is 8 x8. Make the starting vertex your "current" vertex. 2. Choose the first available edge from "current" to a neighbor. o By first available, I mean to the lowest numbered vertex it's connected to. O ERASE this edge (set it to 0) and move along it to update "current" vertex 3. Repeat 2 until you reach the user's goal vertex or you hit a dead end (that is, there are no more moves). 4. Output that you either found a path, or that you hit a dead end. Write your solution in the space below.

Answer 1

File Go Run • grapgh.cpp - startbootstrap-creative-gh-pages - Visual Studio Code Edit Selection View EXTENSIONS: MARKETPLACE Terminal Help * ... <> index.html G+ grapgh.cpp Release Notes: 1.45.0 chekers.mat • G+ grapgh.cpp @id:ms-vscode.cpptools 2 / Traversal for the 2D graph C/C++ 0.28.0 C/C++ IntelliSense, debugging, and code bro... Microsoft #include<bits/stdch.h> using namespace std; //std libaryl // This class represents a directed graph using adjacency // list representation class Graph int V; // No. of vertices list int> *adj; // adjacency lists public: Graph(int v); // Constructor void addEdge(int v, int w); // to add an edge to graph, void DFS(int s); // prints all vertices in DFS manner // from a given source. }; Graph::Graph(int V) this-> = V; adj = new list int>[V]; void Graph::addEdge(int v, int w), adj[v].push_back(w); // Add w to v's list. // prints all not yet visited vertices reachable from s void Graph::DFS(int s) // Initially mark all verices as not visited vector<bool> visited(v, false); O C/C++ Extension: Downloading 1/3: C/C++ language components (Wi... // Create a stack for DFS stack int> stack: ⓇOAO In 5, Col 34 Spaces: 4 UTF-8 CRLF C++ ^JC ») ENG 2:20 AM IN 5/14/2020 3

- 0 X File Edit Selection View Go Run Terminal Help • grapgh.cpp - startbootstrap-creative-gh-pages - Visual Studio Code EXTENSIONS: MARKETPLACE E <> index.html Release Notes: 1.45.0 Echekers.mat • G+ grapgh.cpp G+ grapgh.cpp @id:ms-vscode.cpptools 21 Pines dit HOL yeL VISileu vel lies i taciaule TIONS 32 void Graph::DFS(int s) C/C++ 0.28.0 33 C/C++ IntelliSense, debugging, and code bro... // Initially mark all verices as not visited Microsoft vector<bool> visited(v, false); DL // Create a stack for DFS stack int> stack; // Push the current source node. stack.push(s); while (!stack.empty()) // Pop a vertex from stack and print it s = stack.top(); stack.pop(); // stack may contain same vertex twice. So // we need to print the popped item only // if it is not visited. if (!visited[s]) cout << s << " "; visited[s] = true; // Get all adjacent vertices of the popped vertex s // If a adjacent has not been visited, then push it // to the stack. for (auto i = adj[S].begin(); i != adj[S].end(); ++i) if (!visited[*i]) stack.push(*i); 67 68 // Driver program to test methods of graph class int main() O C/C++ Extension: Downloading 1/3: C/C++ language components (Wi... ⓇOAO In 5, Col 34 Spaces: 4 C UTF-8 CRLF C++ ENG 2:21 AM ^ l. » IN 5/14/20203

File Go Run • grapgh.cpp - startbootstrap-creative-gh-pages - Visual Studio Code - 0 X Edit Selection View EXTENSIONS: MARKETPLACE Terminal Help <> index.html E grapgh.cpp Release Notes: 1.45.0 chekers.mat • G grapgh.cpp @id:ms-vscode.cpptools 01 1 != dusj.en tt1) TOT (dulu 1 = dus .vegi if (!visited[ki]) stack.push(*i); C/C++ 0.28.0 C/C++ IntelliSense, debugging, and code bro... Microsoft 67 // Driver program to test methods of graph class int main() Graph g(5); // Total 5 vertices in graph g.addEdge(1, 0); g.addEdge(0, 2); g.addEdge(2, 1); g.addEdge(0, 3); g.addEdge(1, 4); cout << "Following is Depth First Traversal\n"; g.DFS(); return 0; O C/C++ Extension: Downloading 1/3: C/C++ language components (Wi... ⓇOAO Ln 5, Col 34 Spaces: 4 UTF-8 CRLF C++ am ENG 2:21 AM ^ l. » IN 5/14/20203