Graph Usage

Graph is one of the most common and important data structure. With C++ and STL I'll show you the best possible implementation for graph that you'll be able to implement and analyze in your code at FAANG interviews within the time constraints.

Graph Adjacency List vs Adjacency Matrix

Most of the cases the List representation is good enough, if the graph is sparse then it will take less space, and if the graph is dense you should use the adjacency matrix representation.

In my opinion any graph with less than 70% of the all possible edges: \(\text{Count(E)} \geq 0.7 * {n \choose 2}\) present can be considered to be implemented as adjacency list.

C++ Graph representation

APIs to implement Graph Class

• internal hashtable for the adjacency list representation
• all the edges in a vector, in order to quickly see what are the edges are there?
• function to add edge and a function to add vertices into the graph class.

#include <iostream>
#include <list>
#include <unordered_map>
#include <vector>
#include <utility>

using namespace std;

// Directed graph implementation
class Graph{ 
private:
    unordered_map<char, list<pair<char, int>>> adj_list;
    vector<pair<char, char>> E; // edge set
public:
    vector<pair<char, char>> edges(){
        return E;
    }

    void add_edge(char vertex1, char vertex2, int weight){
        adj_list[vertex1].push_front(make_pair(
            vertex2, weight
        ));

        E.push_back({vertex1, vertex2});
    }

    void register_vertex(vector<char> vertices){
        for (auto v:vertices){
            list<pair<char, int>> l;
            adj_list.insert({v, l});
        }
    }

    unordered_map<char, list<pair<char, int>>> view(){
        return adj_list;
    }
};

The following code shows how to make a graph and use it

int main() {
    Graph g;
    vector<char> v = {'a', 'b', 'c'};
    g.register_vertex(v);
    g.add_edge('a', 'c', 32);
    g.add_edge('a', 'd', 2);
    g.add_edge('b', 'd', 12);
    g.add_edge('b', 'c', 98);
    g.add_edge('c', 'a', 1);

    unordered_map<char, list<pair<char, int>>> map = g.view();

    for (auto data:map){
        cout << data.first << " ";

        for (auto neighbor:data.second)
            cout << "[" << neighbor.first << ": " << neighbor.second << "]";

        cout << "\n";
    }

    // print all the edges
    auto edges = g.edges();
    for (auto edge:edges){
        cout << edge.first << "->" << edge.second << "\n";

    }
}

If you wish to get all the contents in your email please subscribe below.