This question is a follow up to this. I am learning Graph data structure and have implemented DFS and BFS in a way that it can handle data types other than int. These function try to search an end or goal node from a start node.
- How can I design DFS better? As of now, I need to reset visited nodes and flag every time the search happens.
- Any suggestions for improvement of BFS and other parts of code?
- Any logical errors?
The complete commented code is given below:
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
// The Helper function to print and check Adjacency List of the graph
template<typename T>
void print_list(const std::list<T>& l)
{
//typename std::list<T>::const_iterator it;
for(auto it = l.cbegin(); it != l.cend(); it++)
{
std::cout << *it << "\t";
}
std::cout << std::endl;
}
// The class for Graph
template<typename T>
class Graph
{
//Undirected Graph
std::map<T, std::list<T>> adj_list;
public:
Graph(const std::vector<std::pair<T, T>>&);
void add_edge(std::pair<T, T>);
size_t size();
void print_adj_list();
void bfs(T, T);
void dfs(T, T, std::set<T>&, int&);
};
// The graph constructor. Takes in a vector of edges and builds graph.
template<typename T>
Graph<T>::Graph(const std::vector<std::pair<T, T>>& edges)
{
for(size_t i = 0; i < edges.size(); i++)
{
this -> add_edge(edges[i]);
}
}
// Undirected Graph
// Add additional edges specified by pair
template<typename T>
void Graph<T>::add_edge(std::pair<T, T> edge)
{
adj_list[edge.first].push_back(edge.second);
adj_list[edge.second].push_back(edge.first);
}
// Returns no. of vertices / nodes in the graph
template<typename T>
size_t Graph<T>::size()
{
std::cout << "Size of Graph(no. of vertices): " << std::endl;
return adj_list.size();
}
// Function to print Adjacency List with the help of print_list function.
template<typename T>
void Graph<T>::print_adj_list()
{
std::cout << "The Adjacency List: " << std::endl;
//typename std::map<T, std::list<T>>::const_iterator it;
for(auto it = adj_list.cbegin(); it != adj_list.cend(); it++)
{
std::cout << it -> first << "\t";
print_list(it -> second);
}
}
// DFS using queue. The search starts from 'start' node and ends when 'end' node is found or
// the entire graph is traversed. The set `visited` and `flag` needs to be reset before search.
template<typename T>
void Graph<T>::dfs(T start, T end, std::set<T>& visited, int& flag)
{
visited.insert(start);
std::cout << start << "\t";
if(start == end)
{
flag = 1;
std::cout << "Found" << std::endl;
return;
}
if(visited.size() == adj_list.size())
{
std::cout << "Not found" << std::endl;
return;
}
for(auto it = adj_list[start].cbegin(); it != adj_list[start].cend(); it++)
{
if(flag)
{
return;
}
if(visited.find(*it) == visited.end())
{
dfs((*it), end, visited, flag);
}
}
}
// BFS using queue. The search starts from 'start' node and ends when 'end' node is found or
// the entire graph is traversed.
template<typename T>
void Graph<T>::bfs(T start, T end)
{
std::set<T> visited;
std::queue<T> q;
q.push(start);
visited.insert(start);
while(!q.empty())
{
T node = q.front();
q.pop();
std::cout << node << "\t";
if(node == end)
{
std::cout << "Found" << std::endl;
return;
}
for(auto it = adj_list[node].cbegin(); it != adj_list[node].cend(); it++)
{
if(visited.find(*it) == visited.end())
{
q.push(*it);
visited.insert(*it);
}
}
}
std::cout << "Not Found" <<std::endl;
}
//Main
int main()
{
// Uncomment the block below to test with int
/*std::vector<std::pair<int, int>> v;
v.push_back({1, 2});
v.push_back({2, 8});
v.push_back({2, 5});
v.push_back({2, 4});
v.push_back({3, 4});
v.push_back({5, 9});
v.push_back({5, 7});
v.push_back({5, 6});
Graph<int> g{v};*/
// Uncomment the block below to test with char
std::vector<std::pair<char, char>> v;
v.push_back({'a', 'b'});
v.push_back({'b', 'h'});
v.push_back({'b', 'e'});
v.push_back({'b', 'd'});
v.push_back({'c', 'd'});
v.push_back({'e', 'i'});
v.push_back({'e', 'g'});
v.push_back({'e', 'f'});
//Create graph
Graph<char> g{v};
// Check adjacency list by printing it
g.print_adj_list();
// Print size of graph
std::cout << g.size() << std::endl;
// Adding additional edges
g.add_edge({'i', 'k'});
g.add_edge({'f', 'k'});
g.print_adj_list();
std::cout << g.size() << std::endl;
// Test case 1 for DFS and BFS (Result is "Found")
std::set<char>visited;
int flag = 0;
g.dfs('d', 'i', visited, flag);
g.bfs('d', 'i');
// Test case 2 for DFS and BFS (Result is "Found")
flag = 0;
visited.clear();
g.dfs('d', 'c', visited, flag);
g.bfs('d', 'c');
// Test case 3 for DFS and BFS (Result is "Not Found")
flag = 0;
visited.clear();
g.dfs('d', 'q', visited, flag);
g.bfs('d', 'q');
return 0;
}