Breath First Search and Depth First Search are two graph traversal algorithm to search graph items. I provide my implementation for both methods. Code is self explanatory. I also provided a simple graph implementation.
#include <iostream> #include <vector> #include <algorithm> #include <stack> #include <queue> using namespace std; struct Vertex { char name; int number; Vertex(): name('X'), number(-1) {} Vertex(char nm, int nmb) : name(nm), number(nmb) {} }; struct Edge { Vertex vertices[2]; double weight; Edge(const Vertex& v1, const Vertex& v2, double w = 0.0): weight(w) { vertices[0] = v1; vertices[1] = v2; } }; class Graph { vector<Vertex> vertices; vector<Edge> edges; public: void add_vertex(const Vertex& vertex); void add_edge(const Edge& edge); void add_edge(const Vertex& v1, const Vertex& v2); vector<char> breadth_first(Vertex& start); vector<char> depth_first(Vertex& start); vector<Vertex> find_neighbours(const Vertex& v); Vertex& getVertex(char name); void sign_vertex(const char name); }; void Graph::add_vertex(const Vertex &vertex) { vertices.push_back(vertex); } void Graph::add_edge(const Vertex &v1, const Vertex &v2) { edges.push_back(Edge(v1, v2)); } void Graph::add_edge(const Edge &edge) { edges.push_back(edge); } vector<char> Graph::depth_first(Vertex& start) { // pick first neighbour to start stack<Vertex> stk; vector<char> traversal; stk.push(start); while(!stk.empty()) { Vertex& t = stk.top(); sign_vertex(t.name); traversal.push_back(t.name); vector<Vertex> neighbours = find_neighbours(t); vector<Vertex>::iterator it = neighbours.begin(); for(; it != neighbours.end(); it++) { if ((*it).number == 0) { break; } } if (it == neighbours.end()) { stk.pop(); continue; } else { sign_vertex((*it).name); stk.push(*it); } } return traversal; } vector<char> Graph::breadth_first(Vertex& start) { queue<Vertex> q; vector<char> traversal; q.push(start); while(!q.empty()) { Vertex& t = q.front(); sign_vertex(t.name); traversal.push_back(t.name); vector<Vertex> neighbours = find_neighbours(t); for(vector<Vertex>::iterator it = neighbours.begin(); it != neighbours.end(); it++) { if ((*it).number != 0) continue; sign_vertex((*it).name); q.push(*it); } q.pop(); } return traversal; } vector<Vertex> Graph::find_neighbours(const Vertex &v) { vector<Vertex> vec; for(vector<Edge>::iterator it = edges.begin(); it != edges.end(); it++) { if ((*it).vertices[0].name == v.name) { vec.push_back((*it).vertices[1]); } else if ((*it).vertices[1].name == v.name) { vec.push_back((*it).vertices[0]); } } return vec; } Vertex &Graph::getVertex(char name) { vector<Vertex>::iterator it = vertices.begin(); for (; it != vertices.end(); ++it) { if (name == (*it).name) return *it; } return *it; } void Graph::sign_vertex(const char name) { for(vector<Vertex>::iterator it = vertices.begin(); it != vertices.end(); it++) { if (name == (*it).name) { (*it).number = 1; break; } } for(vector<Edge>::iterator it = edges.begin(); it != edges.end(); it++) { if ((*it).vertices[0].name == name) { (*it).vertices[0].number = 1; } else if ((*it).vertices[1].name == name) { (*it).vertices[1].number = 1; } } } int main() { Vertex a('A', 0); Vertex b('B', 0); Vertex c('C', 0); Vertex d('D', 0); Vertex e('E', 0); Edge ab(a, b); Edge bd(b, d); Edge dc(d, c); Edge ac(a, c); Edge ae(a, e); Edge de(d, e); Graph graph; graph.add_vertex(a); graph.add_vertex(b); graph.add_vertex(c); graph.add_vertex(d); graph.add_vertex(e); graph.add_edge(ab); graph.add_edge(bd); graph.add_edge(dc); graph.add_edge(ac); graph.add_edge(ae); graph.add_edge(de); cout << "breath first" << endl; vector<char> traversal = graph.breadth_first(a); for (vector<char>::const_iterator it = traversal.begin(); it != traversal.end() ; ++it) { cout << *it << endl; } return 0; }
Note that depth first search uses stack data structure while breath first search uses queue.
Notice the sign_vertex function. It signs a vertex by assigning vertex’s number a value other than 0. Signing happens in two loops. First loop signs vertices in vertices list, second list maintain vertices hold by edges.