Implementing Breadth First Search Please help me debug this code, the expected output is attached below. #include #include #include #include #include #include template class Graph; Step 2:...

Implementing Breadth First Search

Please help me debug this code, the expected output is attached below.

#include
#include
#include
#include
#include

#include
template
class Graph;
Step 2: Write the following struct, which represents an edge in our graph:
template
struct Edge
{
size_t src;
size_t dest;
T weight;
inline bool operator<(const> &e) const
{
return this->weight <>
}
inline bool operator>(const Edge &e) const
{
return this->weight > e.weight;
}
};

template
std::ostream &operator<(std::ostream &os,="" const=""> &G)
{
for (auto i = 1; i < g.vertices();="">
{
os < i=""><>
auto edges = G.outgoing_edges(i);
for (auto &e : edges)
os < "{"="">< e.dest="">< ":="" "="">< e.weight="">< "},="">
os <>
}
}

template
class Graph
{
public:
Graph(size_t N) : V(N) {}
auto vertices() const
{
return V;
}
auto &edges() const
{
return edge_list;
}
void add_edge(Edge &&e)
{
if (e.src >= 1 && e.src <= v="">
e.dest >= 1 && e.dest <=>
edge_list.emplace_back(e);
else
std::cerr < "vertex="" out="" of="" bounds"=""><>
}
auto outgoing_edges(size_t v) const
{
std::vector<>> edges_from_v;
for (auto &e : edge_list)
{
if (e.src == v)
{
edges_from_v.emplace_back(e);
}
}
return edges_from_v;
}
template
friend std::ostream &operator<(std::ostream &os,="" const=""> &G);
private:
size_t V;
std::vector<>> edge_list;
};

template
auto create_reference_graph()
{
Graph G(9);
std::map<>>> 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{i.first, j.first, j.second});
return G;
}

template
auto breadth_first_search(const Graph &G, size_t dest)
{
std::queue queue;
std::vector visit_order;
std::set 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
void test_BFS()
{
// Create an instance of and print the graph
auto G = create_reference_graph();
std::cout < g=""><>
// Run BFS starting from vertex ID 1 and print the order
// in which vertices are visited.
std::cout < "bfs="" order="" of="" vertices:="" "=""><>
auto bfs_visit_order = breadth_first_search(G, 1);
for (auto v : bfs_visit_order)
std::cout < v=""><>
}
int main()
{
using T = unsigned;
test_BFS();
return 0;
}

3:<br>4:<br>5:<br>6:<br>7:<br>8:<br>A Microsoft Visual Studio Debug Console<br>(2: 2}, (5: 3),<br>{1: 2}, (5: 5), (4: 1},<br>{4: 2}, (7: 3},<br>{2: 1}, {3: 2}, {5: 2}, {6: 4}, {8: 5},<br>{1: 3}, (2: 5}, (4: 2}, (8: 3},<br>(4: 4), (7: 4), (8: 1),<br>{3: 3), (6: 4},<br>{4: 5}, {5: 3}, {6: 1},<br>BFS Order of vertices:<br>

Extracted text: 3: 4: 5: 6: 7: 8: A Microsoft Visual Studio Debug Console (2: 2}, (5: 3), {1: 2}, (5: 5), (4: 1}, {4: 2}, (7: 3}, {2: 1}, {3: 2}, {5: 2}, {6: 4}, {8: 5}, {1: 3}, (2: 5}, (4: 2}, (8: 3}, (4: 4), (7: 4), (8: 1), {3: 3), (6: 4}, {4: 5}, {5: 3}, {6: 1}, BFS Order of vertices:

Jun 11, 2022

SOLUTION.PDF

Implementing Breadth First Search Please help me debug this code, the expected output is attached below. #include #include #include #include #include #include template class Graph; Step 2:...

Get Answer To This Question

Related Questions & Answers

Submit New Assignment