# | Likes | Tech tags | Title | Creator | Created date |
---|---|---|---|---|---|
1 | 0 |
2022-07-29 21:53
|
An \(O(|V| + |E|)\) Breadth-first search algorithm implemented on a resizeable directed graph (\(|V|\) is no. of vertices, \(|E|\) is no. of edges).
#include<vector>
#include<deque>
struct BreadthFirstSearchGraph {
struct Node {
std::vector<Node*> arc;
bool explored = false;
int dist;
};
std::deque<Node> nodes; // We use deque instead of vector so that pointers in `arc` don't get invalidated due to
// reallocation when capacity gets exceeded
Node* add_node() {
nodes.push_back(Node());
return &nodes.back();
}
void add_edge(Node* u, Node* v) {
u->arc.push_back(v);
}
void breadth_first_search(Node* start) {
std::deque<Node*> queue(1, start);
start->explored = true;
start->dist = 0;
while(queue.size() > 0) {
Node* cur = queue.front();
queue.pop_front();
for(Node* next : cur->arc) {
if(!next->explored) {
next->explored = true; // Handle exploration tagging on adding to queue, to optimize queue size
// a bit by preventing a node from being added repeatedly
next->dist = cur->dist + 1;
queue.push_back(next);
}
}
}
}
};
int main() {
BreadthFirstSearchGraph graph;
graph.add_node();
graph.add_node();
graph.add_edge(&graph.nodes[0], &graph.nodes[1]);
// ...
// Populate the graph with add_node and add_edge
graph.breadth_first_search(&graph.nodes[0]); // Assumes node 0 is where we start the search
}
classes | ||
std::deque |
en.cppreference.com | cplusplus.com |
std::vector |
en.cppreference.com | cplusplus.com |
functions | ||
std::deque::front |
en.cppreference.com | cplusplus.com |
std::deque::pop_front |
en.cppreference.com | cplusplus.com |
std::deque::push_back |
en.cppreference.com | cplusplus.com |
std::vector::push_back |
en.cppreference.com | cplusplus.com |
Construct an unweighted graph and perform Breadth-first search on it. Calculate the distance of each node from the starting vertex of the search.