Search for a command to run...
Graph implementation and usage in C++
I go by theroyakash on the internet. I am a computer scientist, with research in high performance algorithms, data structures, distributed systems, and beyond. See my work searching google for theroyakash.
No comments yet. Be the first to comment.
This is a data structure series where I introduce you to popular data structures and their implementations using python and my python based data structure and algorithms library AKDSFramework.
Build and run algorithms on Priority Queues (as binary heaps) with just a few lines of code with AKDSFramework.
Clearing pre order, in order and post order traversal confusion under 2 minutes
Setup audio version of your articles for free.
![Set-up an audio version of your blog articles [Works Automatically]](/_next/image?url=https%3A%2F%2Fcdn.hashnode.com%2Fres%2Fhashnode%2Fimage%2Fupload%2Fv1612940767582%2F0abS3UT_8.png&w=3840&q=75)
Build and run algorithms on Priority Queues (as binary heaps) with just a few lines of code with AKDSFramework.
Introducing an efficient Big O analyzer, a premium state-of-the-art AKDSFramework feature to analyze Big O for any function without any human intervention. As you already know calculating big O is a big part of what we do to approximate the running t...
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.
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.
APIs to implement 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.