Here goes the depth first search:
#include <vector>
#include <iostream>
using namespace std;
typedef vector<vector<int> > graph; // adjacency list, vertexs are integers
void dfs(graph g, int s0) // s0 is the first vertex in the search
{
int n = g.size();
if(s0 < 0 || s0 >= n) // invalid initial vertex
return;
vector<bool> already_seen(n, false);
vector<int> to_be_handled {};
to_be_handled.push_back(s0);
while(to_be_handled.size() > 0)
{
int s = to_be_handled.back();
to_be_handled.pop_back();
if(!already_seen[s])
{
already_seen[s] = true;
cout << s << " "; // handle s
for(int v: g[s]) // add neighbors
to_be_handled.push_back(v); // (*)
}
}
}
And for the breadth first search, just replace the line (*) with this line:
to_be_handled.insert(to_be_handled.begin(), v);
I guess using a queue would be more effective for the BFS but I initially just wanted to implement a DFS so don't mind the second one.
std:queue
andstd::stack
. \$\endgroup\$