Programming Traversal Methods in C++ (depth first & breadth first)
Need solution ASAP any help is much appreciated.
read a set of data representing a directed, unweighted graph
build an in-memory graph structure using the data
display the graph using depth-first
traversal
display the graph using breadth-first
traversal
Input data -
The data consists of records like this: 16 3 15 4 -1
This represents a vertex 16 with neighbors 3, 15, and 4. The -1 is the indicator that no more neighbors for this vertex exist. A vertex with no edges would be represented as follows:
12 -1
Vertex 12 has no edges.
Graph data structure-
The graph data structure is an adjacency list using STL vectors as the underlying structure. It’s based on this struct which represents a vertex:
struct Vertex
int vertexValue;
bool visited;
vector neighbors;
Each vertex has some integer value. There is no relationship between a vertex’s value and its position in the vector; the vertex element 6 might be for the vertex with value 13. Each vertex has some number of neighbors. You don’t know in advance how many vertices will be in the graph, and you don’t know how many neighbors a vertex will have, so it makes sense to have a data structure which is completely flexible in both dimensions. See the “vector of vectors” cheat sheet for examples of how this is coded in C++.
Build and populate the graph-
Main will instantiate the graph. Code a function named buildGraph, which is passed the graph: void buildGraph (vector name)
buildGraph opens the data file. If the open fails, display an error message and exit. For each data record, one vertex is created. You may assume that the data is valid and that each value is separated by spaces. (This means you can use the >> operator). You may also assume that the graph contains at least one vertex.
Before returning, buildGraph should display the graph to make sure that it has been built correctly. See the sample output at the end for an example. It is highly recommended that you code and test buildGraph thoroughly before continuing.
buildGraph builds a data structure that contains vertices, each with a unique value. As stated earlier, there is no relationship between the value of a vertex and its position in the data structure. Therefore, you cannot use the vertex value as the index (subscript) into the graph data structure. Although this assignment uses integer values, the values could as easily be strings, or even other data structures. You will therefore need a table lookup function, which, given a vertex value, returns the index into the vector for the vertex with that value.
Depth-first traversal-
After building the graph, main calls function dft to traverse the graph: void dft (vector name)
dft traverses the graph starting with the first vertex. The first vertex is defined as the first vertex in the graph vector. dft loops through the vertices and calls dftInternal repeatedly with a new vertex each time. dftInternal, in turn, processes all the neighbors for that vertex.
dft is actually a helper function for dftInternal, which is recursive: void dftInternal (vector name, vertex)
When called, dftInternal processes all the neighbors for whichever vertex which has been passed as a parameter. It loops through all its neighbors. A given neighbor might have already been visited; in this case, dftInternal goes on to the next neighbor. Otherwise, it calls itself when it finds a neighbor that has not already been visited.
Refer to the class discussion and the logic to understand how to code dft and dftInternal.
Breadth-first traversal-
The function bft traverses the graph using the breadth-first method: void bft (vector name)
Like dft, bft starts with the first vertex, which is defined as the first vertex in the graph vector. bft is iterative (as opposed to recursive) and uses a queue to keep track of which vertices to process.
bst loops through all the vertices, pushing
a vertex onto the queue when it finds one that has not yet been
visited. Within that loop, it empties the queue, processing each
vertex by pushing any neighbors that have not been visited into the
queue. In this manner, all the vertices are pushed onto the queue
in breadth-first order. As the queue is emptied, the neighbors for
each vertex are examined to determine if they have been
visited.
If not, they are added to the queue and the process
continues.
Use your queue class from assignment 6 as the queue implementation.
Refer to the class discussion and the logic to understand how to code bft.
Main-
Code a main which instantiates the graph data structure. Main then calls buildGraph, dft, and bft, and exits. The output should resemble something like this (if using the graph from Malik p.696):
Populated graph:
vertex number 0 value 0 neighbors-> 1 5 vertex number 1 value 1 neighbors-> 2 3 5 vertex number 2 value 2 neighbors-> 4 vertex number 3 value 3 neighbors-> vertex number 4 value 4 neighbors-> 3 vertex number 5 value 5 neighbors-> 6 vertex number 6 value 6 neighbors-> 8 vertex number 7 value 7 neighbors-> 8 3 vertex number 8 value 8 neighbors-> 10 vertex number 9 value 9 neighbors-> 4 7 10 vertex number 10 value 10 neighbors->
Depth-first traversal: 0 1 2 4 3 5 6 8 10 7 9 Breadth-first traversal: 0 1 5 2 3 6 4 8 10 7 9 Have a great day!
HERE is the data.txt file
0 1 5 -1
1 2 3 5 -1
2 4 -1
3 -1
4 3 -1
5 6 -1
6 8 -1
7 8 3 -1
8 10 -1
9 4 7 10 -1
10 -1
Output
Code with comments
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
struct Vertex{ //vertex structure
int vertexValue;
bool visited;
vector<int>neighbor;
};
void buildGraph(vector<Vertex>&graph){ //build graph
fstream file;
file.open("data.txt");
if(!file){
cout<<"File couldn't be opened!!";
exit(0);
}
int count=0;
string line;
while(getline(file,line)) //count lines in graph to determine number of vertices
count++;
file.close();
file.open("data.txt");
for(int i=0;i<count;i++){ //for each vertex
int vertexValue; //read value
file>>vertexValue;
vector<int>neighbor;
int x;
while(file>>x && x!=-1) //read all neighbor till -1
neighbor.push_back(x);
graph.push_back({vertexValue,false,neighbor}); //create and add vertex to graph
cout<<"Vertex number "<<i<<" value "<<vertexValue<<" neighbors->";
for(int i:neighbor)
cout<<i<<" ";
cout<<endl;
}
}
void dftInternal(vector<Vertex>&graph,int vertex){
if(graph[vertex].visited) //visited node
return;
graph[vertex].visited=true; //mark visited
cout<<graph[vertex].vertexValue<<" ";
for(int i:graph[vertex].neighbor) //claa dftInternal on neighbor
dftInternal(graph,i);
}
void dft(vector<Vertex>&graph){
cout<<"Depth-first Traversal:\n";
for(int i=0;i<graph.size();i++) //call dftInterna on each unvisited node to cover all connected components
dftInternal(graph,i);
}
void bft(vector<Vertex>&graph){
cout<<"\nBreadth-first Traversal:\n";
for(int i=0;i<graph.size();i++) //mark all unvivited
graph[i].visited=false;
queue<int>q;
q.push(0); //push initial vertex
graph[0].visited=true;
label: //for bfs on connected components
while(!q.empty()){
int cur=q.front();
q.pop();
cout<<cur<<" ";
for(int i:graph[cur].neighbor){ //add neighbor to queue
if(!graph[i].visited){
graph[i].visited=true;
q.push(i);
}
}
}
for(int i=0;i<graph.size();i++){
if(!graph[i].visited){ //if any vertex left, go back to label
graph[i].visited=true;
q.push(i);
goto label;
}
}
}
int main(){
//function calling
vector<Vertex>graph;
buildGraph(graph);
dft(graph);
bft(graph);
}
For Indentation Purpose
Programming Traversal Methods in C++ (depth first & breadth first) Need solution ASAP any help is...
Creating a simple graph in C++; need solution ASAP. EDIT: Pls comment letting me know what other information you need rather than just "..." Thank you. Here is the assignment: In this final practice problem, you’ll: read a set of data representing a directed, unweighted graph build an in-memory graph structure using the data display the graph using depth-first traversal display the graph using breadth-first traversal Input data - The data consists of records like this: 16 3 15 4...
For the following graph, give the result of any one breadth-first traversal beginning at A, where the label of a vertex is printed when the vertex is visited. A 8 4 7 1 D 2 3 N E F
For the following graph, give the result of any one breadth-first traversal beginning at A, where the label of a vertex is printed when the vertex is visited. A 00 4 7 B с D 2 2 3 E F
In Python 3 please
Apply Breadth First Search (BFS) to traverse the following graph. Start your traversal from vertex 0, and write down the order in which vertices will be visited during the traversal. 1 8 6 7 2 9 5 4 3
(5 marks) a. The pseudo-code for breadth-first search, modified slightly from Drozdek,1 is as follows: void breadthFirstSearch (vertex w) for all vertices u num (u) 0 null edges i=1; num (w) i++ enqueue (w) while queue is not empty dequeue ( V= for all vertices u adjacent to v if num(u) is 0 num (u) = i++; enqueue (u) attach edge (vu) to edges; output edges; Now consider the following graph. Give the breadth-first traversal of the graph, starting from...
C++ Questions: 4) A graph-traversal algorithm stops when it ______. a) first encounters the designated destination vertex b) has visited all the vertices that it can reach c) has visited all the vertices d) has visited all the vertices and has returned to the origin vertex 5) In the following STL declaration of an adjacency list, what does the map pair represent? a) vector<map<int, int> >adjList; b) the first vertex (key) and the edge weight (value) c) the second vertex...
(c) Simulate breadth first search on the graph shown in Fig
HW2Q1c. You can assume that the starting vertex is 1, and the
neighbors of a vertex are examined in increasing numerical order
(i.e. if there is a choice between two or more neighbors, we pick
the smaller one). You have to show: both the order in which the
vertices are visited and the breadth first search tree. No
explanations necessary.
(d) On the same graph, i.e. the graph in...
Question 3 1 pts Select all of the following that are true: Breadth-First Search only adds each vertex to the queue once. Breadth-First Search generally uses more space compared to Depth-First search. Breadth-First Search may not find the shortest path for an unweighted graph if the graph contains a cycle. At any time during Breadth-First Search, the queue holds at most two distinct dist values from all vertices in
from collections import defaultdict # This class represents a directed graph using # adjacency list representation class Graph: # Constructor def __init__(self): # default dictionary to store graph self.graph = defaultdict(list) # function to add an edge to graph def addEdge(self,u,v): self.graph[u].append(v) # Function to print a BFS of graph def BFS(self, s): # Mark all the vertices as not visited visited = [False] * (len(self.graph)) # Create a queue for BFS queue...
In the breadth first traversal procedure BFS, each vertex
v has an attribute v.color. Modify BFS
so that instead of x.color, each vertex
x has a Boolean attribute called x.mark,
whose value is either TRUE or FALSE. The attribute
x.mark must be FALSE if x has never been
visited. It must be TRUE if x has been visited, but will
not be visited again.
Thank you!!!
BFS(G, s) 1 for each vertex u e G.V-(s 11, color WHITE 4 5...