Implementing Depth First Search Please help me debug this code, expected output is attached below. #include #include #include #include #include #include template class Graph; template struct...

Implementing Depth First Search

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

#include
#include
#include
#include
#include

#include
template
class Graph;

template
struct Edge
{
size_t src;
size_t dest;
T weight;
// To compare edges, only compare their weights,
// and not the source/destination vertices
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 <>
}
return os;
}

template
class Graph
{
public:
// Initialize the graph with N vertices
Graph(size_t N) : V(N)
{
}
// Return number of vertices in the graph
auto vertices() const
{
return V;
}
// Return all edges in the graph
auto &edges() const
{

return edge_list;
}
void add_edge(Edge &&e)
{
// Check if the source and destination vertices are within range
if (e.src >= 1 && e.src <= v="">
e.dest >= 1 && e.dest <=>
edge_list.emplace_back(e);
else
std::cerr < "vertex="" out="" of="" bounds"=""><>
}
// Returns all outgoing edges from vertex v
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;
}
// Overloads the < operator="" so="" a="" graph="" be="" written="" directly="" to="" a="">
// Can be used as std::cout < obj=""><>
template
friend std::ostream &operator<>(std::ostream &os, const Graph &G);
private:
size_t V; // Stores number of vertices in graph
std::vector<>> edge_list;
};

template
auto depth_first_search(const Graph &G, size_t dest)
{
std::stack stack;
std::vector visit_order;
std::set visited;
stack.push(1); // Assume that DFS always starts from vertex ID 1
while (!stack.empty())
{
auto current_vertex = stack.top();
stack.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))
{
// If the vertex hasn't been visited, insert it in the
stack.if (visited.find(e.dest) == visited.end())
{
stack.push(e.dest);
}
}
}
}
return visit_order;
}

template
auto create_reference_graph()
{
Graph G(9);
std::map<>>> edges;
edges[1] = {{2, 0}, {5, 0}};
edges[2] = {{1, 0}, {5, 0}, {4, 0}};
edges[3] = {{4, 0}, {7, 0}};
edges[4] = {{2, 0}, {3, 0}, {5, 0}, {6, 0}, {8, 0}};
edges[5] = {{1, 0}, {2, 0}, {4, 0}, {8, 0}};
edges[6] = {{4, 0}, {7, 0}, {8, 0}};
edges[7] = {{3, 0}, {6, 0}};
edges[8] = {{4, 0}, {5, 0}, {6, 0}};
for (auto &i : edges)
for (auto &j : i.second)
G.add_edge(Edge{i.first, j.first, j.second});
return G;
}

template
void test_DFS()
{
// Create an instance of and print the graph
auto G = create_reference_graph();
std::cout < g=""><>
// Run DFS starting from vertex ID 1 and print the order
// in which vertices are visited.
std::cout < "dfs="" order="" of="" vertices:="" "=""><>
auto dfs_visit_order = depth_first_search(G, 1);
for (auto v : dfs_visit_order)
std::cout < v=""><>
}
int main()
{
using T = unsigned;
test_DFS();
return 0;
}

Extracted text: A Microsoft Visual Studio Debug Console {2: 0}, {5: ®}, (1: ej, (5: ej, {4: 0}, {4: 0}, {7: e}, {2: 0}, {3: 0}, {5: 0}, {6: e}, {8: 0}, {1: 0}, {2: e}, {4: 0}, {8: 0}, {4: e}, {7: e}, {8: e}, {3: 0}, {6: 0}, {4: 0}, {5: 0}, {6: 0}, 6: 7: 8: DFS Order of vertices: 1 5 %3A2

Jun 11, 2022

SOLUTION.PDF

Implementing Depth First Search Please help me debug this code, expected output is attached below. #include #include #include #include #include #include template class Graph; template struct...

Get Answer To This Question

Related Questions & Answers

Submit New Assignment