# | Likes | Tech tags | Title | Creator | Created date |
---|---|---|---|---|---|
1 | 0 |
2022-07-29 18:18
|
An \(O(|V| + |E|)\) Depth-first search algorithm implemented on a resizeable and directed graph (\(|V|\) is no. of vertices, \(|E|\) is no. of edges).
Caveat: The algorithm is recursive, which means the function calls get stored in the call stack. The maximum call-stack size is usually 1MB on Windows and 10MB on Linux, which can set a severe restriction on the maximum depth the algorithm can reach before the program crashes. To get around it, either increase the size of the call stack for the program, or use an iterative algorithm instead.
#include<vector>
#include<deque>
#include<algorithm>
struct DepthFirstSearchGraph {
struct Node {
std::vector<Node*> arc;
bool explored = false;
};
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);
}
int depth_first_search(Node* cur, Node* prev = 0) {
// Recursive depth first search that returns the max depth it reaches
int max_depth = 0;
cur->explored = true;
for(Node* next : cur->arc) {
if(!next->explored) {
max_depth = std::max(max_depth, depth_first_search(next, cur)+1);
}
}
return max_depth;
}
};
int main() {
DepthFirstSearchGraph 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
int max_depth = graph.depth_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::push_back |
en.cppreference.com | cplusplus.com |
std::max |
en.cppreference.com | cplusplus.com |
std::vector::push_back |
en.cppreference.com | cplusplus.com |
Construct a graph and perform Depth-first search on it. Return the maximum depth the search reaches.