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.