BFS, DFS

main.cpp

#include <iostream>
#include <utility>
#include <algorithm>
#include <list>
#include <iostream>
#include <map>
#include <stdexcept>
#include <vector>
#include <functional>
#include <queue>

using namespace std;

class Graph
{
public:
    map<int, vector<int>> vertices_edges;

    bool vertex_exists(int vertex)
    {
        return vertices_edges.find(vertex) != vertices_edges.end();
    }

    bool edge_exists(int vertex_a, int vertex_b)
    {
        if (!vertex_exists(vertex_a) || !vertex_exists(vertex_b))
            return false;

        vector<int> &edges_a = vertices_edges.at(vertex_a);
        vector<int> &edges_b = vertices_edges.at(vertex_b);

        return (find(edges_a.begin(), edges_a.end(), vertex_b) != edges_a.end()) && (find(edges_b.begin(), edges_b.end(), vertex_a) != edges_b.end());
    }

    void add_vertex(int vertex)
    {
        if (!vertex_exists(vertex))
            vertices_edges[vertex];
    }

    void remove_vertex(int vertex)
    {
        if (!vertex_exists(vertex))
            return;

        vertices_edges.erase(vertex);

        for (auto &item : vertices_edges)
        {
            vector<int> &edges = item.second;
            edges.erase(remove(edges.begin(), edges.end(), vertex), edges.end());
        }
    }

    void add_edge(int vertex_a, int vertex_b)
    {
        if (!edge_exists(vertex_a, vertex_b))
        {
            vertices_edges.at(vertex_a).push_back(vertex_b);
            vertices_edges.at(vertex_b).push_back(vertex_a);
        }
    }

    void remove_edge(int vertex_a, int vertex_b)
    {
        vector<int> &edges_a = vertices_edges.at(vertex_a);
        vector<int> &edges_b = vertices_edges.at(vertex_b);

        edges_a.erase(remove(edges_a.begin(), edges_a.end(), vertex_b), edges_a.end());
        edges_b.erase(remove(edges_b.begin(), edges_b.end(), vertex_a), edges_b.end());
    }

    void print()
    {
        for (auto &item : vertices_edges)
        {
            cout << item.first << " | ";
            for (auto &edge : item.second)
            {
                cout << edge << ", ";
            }

            cout << endl;
        }
    }

    vector<int> DFS(const int start)
    {
        vector<int> visited;

        function<void(int)> traverse = [&](int root_vertex)
        {
            visited.push_back(root_vertex);
            for (int &vertex : vertices_edges.at(root_vertex))
                if (find(visited.begin(), visited.end(), vertex) == visited.end())
                    traverse(vertex);
        };

        traverse(start);
        return visited;
    }

    vector<int> BFS(const int start)
    {
        vector<int> visited = {start};
        queue<int> queue_{{start}};

        while (!queue_.empty())
        {
            int root_vertex = queue_.front();
            queue_.pop();

            for (int &vertex : vertices_edges.at(root_vertex))
                if (find(visited.begin(), visited.end(), vertex) == visited.end())
                {
                    visited.push_back(vertex);
                    queue_.push(vertex);
                }
        }

        return visited;
    }
};

int main()
{
    Graph graph;

    {
        for (int i = 0; i < 5; ++i)
            graph.add_vertex(i);

        graph.add_edge(1, 2);
        graph.add_edge(1, 3);
        graph.add_edge(2, 4);

        graph.add_vertex(1);
        graph.add_edge(1, 2);


        graph.print();
    }

    cout << endl;

    {
        vector<int> dfs_result = graph.DFS(1);

        cout << "DFS: ";
        for (int &vertex : dfs_result)
            cout << vertex << ", ";
    }

    cout << endl;

    {
        vector<int> bfs_result = graph.BFS(1);

        cout << "BFS: ";
        for (int &vertex : bfs_result)
            cout << vertex << ", ";
    }

    return 0;
}