In this code, what data structure is used to implement the Breadth First Search?
In this code, what data structure is used to implement the Breadth First Search?
#include <string>
#include <
#include <iostream>
#include <set>
#include <map>
#include <queue>
template < typename T >
class Graph;
template < typename T >
struct Edge {
size_t src;
size_t dest;
T weight;
inline bool operator < (const Edge < T > & e) const {
return this -> weight < e.weight;
}
inline bool operator > (const Edge < T > & e) const {
return this -> weight > e.weight;
}
};
template < typename T >
std::ostream & operator << (std::ostream & os, const Graph < T > & G) {
for (auto i = 1; i < G.vertices(); i++) {
os << i << ":\t";
auto edges = G.outgoing_edges(i);
for (auto & e: edges)
os << "{" << e.dest << ": " << e.weight << "}, ";
os << std::endl;
}
// below line is added
// after performing you have to return the ostream
return os;
}
template <typename T>
class Graph {
public:
Graph(size_t N): V(N) {}
auto vertices() const {
return V;
}
auto & edges() const {
return edge_list;
}
void add_edge(Edge < T > && e) {
if (e.src >= 1 && e.src <= V &&
e.dest >= 1 && e.dest <= V)
edge_list.emplace_back(e);
else
std::cerr << "Vertex out of bounds" << std::endl;
}
auto outgoing_edges(size_t v) const {
std::vector < Edge < T >> edges_from_v;
for (auto & e: edge_list) {
if (e.src == v) {
edges_from_v.emplace_back(e);
}
}
return edges_from_v;
}
template < typename Type > // here change typename T to typename Type because
// same T is also declared above for class
// and that's is ambiguous to the compiler so compiler will
// generate error so change the new template name to something
// different than the class template
friend std::ostream & operator << (std::ostream & os, const Graph < Type > & G);
private:
size_t V;
std::vector < Edge < T >> edge_list;
};
template < typename T >
auto create_reference_graph() {
Graph < T > G(9);
std::map < unsigned, std::vector < std::pair < size_t, T >>> edges;
edges[1] = {{2, 2}, {5, 3}};
edges[2] = {{1, 2}, {5, 5}, {4, 1}};
edges[3] = {{4, 2}, {7, 3}};
edges[4] = {{2, 1}, {3, 2}, {5, 2}, {6, 4}, {8, 5}};
edges[5] = {{1, 3}, {2, 5}, {4, 2}, {8, 3}};
edges[6] = {{4, 4}, {7, 4}, {8, 1}};
edges[7] = {{3, 3}, {6, 4}};
edges[8] = {{4, 5}, {5, 3}, {6, 1}};
for (auto & i: edges)
for (auto & j: i.second)
G.add_edge(Edge < T > {
i.first,
j.first,
j.second
});
return G;
}
template < typename T >
auto breadth_first_search(const Graph < T > & G, size_t dest) {
std::queue < size_t > queue;
std::vector < size_t > visit_order;
std::set < size_t > visited;
queue.push(1); // Assume that BFS always starts from vertex ID 1
while (!queue.empty()) {
auto current_vertex = queue.front();
queue.pop();
// If the current vertex hasn't been visited in the past
if (visited.find(current_vertex) == visited.end()) {
visited.insert(current_vertex);
visit_order.push_back(current_vertex);
for (auto e: G.outgoing_edges(current_vertex))
queue.push(e.dest);
}
}
return visit_order;
}
template < typename T >
void test_BFS() {
// Create an instance of and print the graph
auto G = create_reference_graph < unsigned > ();
std::cout << G << std::endl;
// Run BFS starting from vertex ID 1 and print the order
// in which vertices are visited.
std::cout << "BFS Order of vertices: " << std::endl;
auto bfs_visit_order = breadth_first_search(G, 1);
for (auto v: bfs_visit_order)
std::cout << v << std::endl;
}
int main() {
using T = unsigned;
test_BFS <T> ();
return 0;
}
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 7 images
