# Breath First Search & Depth First Search

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.