Show Menu

C++ Graph Theory Sample Cheat Sheet by

Some sample graph theory code that can be used
c-     graph

Repres­ent­ation

///Adjacency Matrix////////////////////
int V, E, A, B, W, g[1005][1005];
cin >> V >> E; memset(g, -1, sizeof(g));
for (int i = 0; i < E; i++) {
    cin >> A >> B >> W;
    //Weight, can set for both or single direction
    g[A][B] = W;
    g[B][A] = W;
}

///Adjacency List//////////////////////
vector<pair<int, int> > g[1005];
int V, E, A, B, W;
cin >> V >> E;
for (int i = 0; i < E; i++) {
    cin >> A >> B >> W;
    g[A].push_back(make_pair(B, W));
    g[B].push_back(make_pair(A, W));
}

Floyd-­War­shall

//initialise dist[i][j] to infinity at the start
for (int k=0;k<n;k++)
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
        // if there is a shorter path through node k, take it!
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);w
Floyd-­War­shall algorithm uses the idea of triangle inequa­lity, and is very
easy to code (just 4 lines!)

If there are negative cycles, dist[i][i] will be negative. Note the order!!!
 

Breadth First Search

vector<int> g[100005];
queue<pair<int, int> > q;
int dist[1000005];
fill(dist, dist+1000005, -1);
while (!q.empty()) {
    int v = q.front().first;
    int d = q.front().second;
    q.pop();
    if (dist[v] != -1) continue; //Visited
    dist[v] = d;
    for (int i = 0; i < g[v].size(); i++) {
        q.push(make_pair(g[v][i], d+1));
    }
}
Time Comple­xity: O(|V| + |E|)
Space Comple­xity: O(b^d)
where d is the depth of the graph and b is the branching factor.

BFS is more suitable when the goal is close to the source, BFS is still faster in such cases.

We can use this algorithm to find the shortest path in a grid/u­nwe­ighted
graph

Bellma­n-Ford

dist[s]=0; //dist all others = INF
for (int i=0; i<N-1; i++){
    for (int j=0; j<E; j++){
        // if path is shorter through node u, take it!
        dist[v] = min(dist[v], dist[u]+cost);
    }
}
Solves the Single Source Shortest Path (SSSP) problem. (shortest path from one node (source) to all other nodes)
Can be used with negative edges, Run the algorithm twice to detect for negative cycles

Time Comple­xity: O(VE)
Space Comple­xity: O(V)
 

Depth First Search

bool vis[N];
vector<int> adjList[N];
void dfs(int node) {
    if (vis[node]) return;
    vis[node] = true;
    for (int a = 0; a < (int)adjList[node].size(); ++a)
        dfs(adjList[node][a]);
}

///Iterative////////////////////////////////
bool vis[N];
vector<int> adjList[N];
stack<int> S;
while (!S.empty()) {
    int node = S.top();
    S.pop();
    if (vis[node]) continue;
    vis[node] = true;
    for (int a = 0; a < (int)adjList[node].size(); ++a)
        S.push(adjList[node][a]);
}
DFS uses O(d) space, where d is the depth of the graph

DFS is not suited for infinite graphs.

Some applic­ations of DFS include:
1. Topolo­gical Ordering (covered later)
2. Pre-/I­n-/­Pos­t-order numbering of a tree
3. Graph connec­tivity
4. Finding articu­lation points
5. Finding bridges

Dijkstra's Algorithm

vector<pair<int,int> > adjList[10000]; // node, weight
priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq; // distance, node
int dist[10000];
memset(dist, -1, sizeof(dist));
pq.push(make_pair(0, source)); dist[0] = 0;
while(!pq.empty()){
    pair<int,int> c = pq.top();
    pq.pop();
    if(c.first != dist[c.second]) continue;
    for(auto i : adjList[c.second]){
        if(dist[i.first] == -1 || dist[i.first] > c.first + i.second){
            dist[i.first] = c.first + i.second;
            pq.push(make_pair(dist[i.first], i.first));
        }
    }
}
Time Complexity of our implem­ent­ation: O(E log E)
Space Comple­xity: O(V+E)

Solves the Single Source Shortest Path (SSSP) problem. Means shortest path from one node to all other nodes. Cannot be used with negative edges as it runs too slow
Especially cannot be used with negative cycles

Download the C++ Graph Theory Sample Cheat Sheet

2 Pages
//media.cheatography.com/storage/thumb/hackin7_c-graph-theory-sample.750.jpg

PDF (recommended)

Alternative Downloads

Share This Cheat Sheet!

 

Comments

No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.

          Related Cheat Sheets

          Numeric Formats Cheat Sheet
          C# & Unity MonoBehaviour Cheat Sheet

          More Cheat Sheets by Hackin7