Graph Algorithms Deep Dive Key Concepts and Techniques

Created on August 15, 2024

2024   ·   formatting   code   ·   sample-posts

  1. Graph Representation
    • Adjacency Matrix
    • Adjacency List
  2. Graph Traversal
    • BFS
    • DFS
  3. Topological Sort
    • Using DFS
    • Kahn’s Algorithm
  4. Shortest Path Algorithms
    • Dijkstra’s Algorithm
    • Bellman-Ford
    • Floyd-Warshall
  5. Union-Find / Disjoint Set
  6. Minimum Spanning Tree
    • Prim’s Algorithm
    • Kruskal’s Algorithm
  7. Cycle Detection
    • Undirected Graph
    • Directed Graph
  8. Bipartite Graph

Graph Representation

1. Adjacency Matrix

2. Adjacency List

C++ Code for both representations:

#include <iostream>#include <vector>using namespace std;


void adjacencyMatrix(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adjMatrix(n, vector<int>(n, 0));
    for (auto& edge : edges) {
        int u = edge[0];
        int v = edge[1];
        adjMatrix[u][v] = 1;
        adjMatrix[v][u] = 1; 
    }

    for (auto row : adjMatrix) {
        for (auto val : row) cout << val << " ";
        cout << endl;
    }
}


void adjacencyList(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adjList(n);
    for (auto& edge : edges) {
        int u = edge[0];
        int v = edge[1];
        adjList[u].push_back(v);
        adjList[v].push_back(u); 
    }

    for (int i = 0; i < n; i++) {
        cout << i << ": ";
        for (int v : adjList[i]) cout << v << " ";
        cout << endl;
    }
}

Practice Problems:

  1. LeetCode 133: Clone Graph
  2. LeetCode 797: All Paths From Source to Target
  3. LeetCode 207: Course Schedule
  4. LeetCode 1557: Minimum Number of Vertices to Reach All Nodes
  5. LeetCode 1466: Reorder Routes to Make All Paths Lead to the City Zero

Graph Traversals (BFS and DFS)

C++ Code:

#include <iostream>#include <vector>#include <queue>using namespace std;

// BFS
void bfs(int start, vector<vector<int>>& adjList, int n) {
    vector<bool> visited(n, false);
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";

        for (int neighbor : adjList[node]) {
            if (!visited[neighbor]) {
                q.push(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

// DFS
void dfs(int node, vector<vector<int>>& adjList, vector<bool>& visited) {
    visited[node] = true;
    cout << node << " ";

    for (int neighbor : adjList[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, adjList, visited);
        }
    }
}

Practice Problems:

  1. LeetCode 200: Number of Islands
  2. LeetCode 994: Rotting Oranges
  3. LeetCode 103: Binary Tree Zigzag Level Order Traversal
  4. LeetCode 130: Surrounded Regions
  5. LeetCode 1306: Jump Game III

Topological Sort

1. Using DFS

2. Kahn’s Algorithm

C++ Code:

#include <iostream>#include <vector>#include <stack>#include <queue>using namespace std;

// Topological Sort using DFS
void topoSortDFS(int node, vector<vector<int>>& adjList, vector<bool>& visited, stack<int>& st) {
    visited[node] = true;

    for (int neighbor : adjList[node]) {
        if (!visited[neighbor]) {
            topoSortDFS(neighbor, adjList, visited, st);
        }
    }
    st.push(node);
}

vector<int> topologicalSortDFS(int n, vector<vector<int>>& adjList) {
    vector<bool> visited(n, false);
    stack<int> st;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            topoSortDFS(i, adjList, visited, st);
        }
    }

    vector<int> topoOrder;
    while (!st.empty()) {
        topoOrder.push_back(st.top());
        st.pop();
    }
    return topoOrder;
}

// Topological Sort using Kahn's Algorithm (BFS)
vector<int> topologicalSortKahn(int n, vector<vector<int>>& adjList) {
    vector<int> inDegree(n, 0);
    for (int i = 0; i < n; i++) {
        for (int neighbor : adjList[i]) {
            inDegree[neighbor]++;
        }
    }

    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) q.push(i);
    }

    vector<int> topoOrder;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        topoOrder.push_back(node);

        for (int neighbor : adjList[node]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) q.push(neighbor);
        }
    }
    return topoOrder;
}

Practice Problems:

  1. LeetCode 210: Course Schedule II
  2. LeetCode 802: Find Eventual Safe States
  3. LeetCode 329: Longest Increasing Path in a Matrix
  4. LeetCode 1136: Parallel Courses
  5. LeetCode 1203: Sort Items by Groups Respecting Dependencies

Shortest Path Algorithms

1. Dijkstra’s Algorithm

2. Bellman-Ford

3. Floyd-Warshall

C++ Code:

#include <iostream>#include <vector>#include <queue>#include <climits>using namespace std;

// Dijkstra's Algorithm
vector<int> dijkstra(int n, vector<vector<pair<int, int>>>& adjList, int start) {
    vector<int> dist(n, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        for (auto& neighbor : adjList[u]) {
            int v = neighbor.first;
            int weight = neighbor.second;

            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

// Bellman-Ford Algorithm
vector<int> bellmanFord(int n, vector<vector<int>>& edges, int start) {
    vector<int> dist(n, INT_MAX);
    dist[start] = 0;

    for (int i = 1; i <= n - 1; i++) {
        for (auto& edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int weight = edge[2];

            if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                dist[v] =

 dist[u] + weight;
            }
        }
    }
    return dist;
}

// Floyd-Warshall Algorithm
vector<vector<int>> floydWarshall(int n, vector<vector<int>>& graph) {
    vector<vector<int>> dist = graph;

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    return dist;
}

Practice Problems:

  1. LeetCode 743: Network Delay Time
  2. LeetCode 787: Cheapest Flights Within K Stops
  3. LeetCode 1631: Path With Minimum Effort
  4. LeetCode 1514: Path with Maximum Probability
  5. LeetCode 1129: Shortest Path with Alternating Colors

Union-Find / Disjoint Set

C++ Code:

#include <iostream>#include <vector>using namespace std;

class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;

public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }

    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
};

Practice Problems:

  1. LeetCode 684: Redundant Connection
  2. LeetCode 990: Satisfiability of Equality Equations
  3. LeetCode 721: Accounts Merge
  4. LeetCode 1319: Number of Operations to Make Network Connected
  5. LeetCode 128: Longest Consecutive Sequence

Minimum Spanning Tree

1. Prim’s Algorithm

2. Kruskal’s Algorithm

C++ Code:


#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

// Prim's Algorithm
int primMST(int n, vector<vector<pair<int, int>>>& adjList) {
    vector<bool> inMST(n, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    int mstCost = 0;

    pq.push({0, 0}); // (cost, node)

    while (!pq.empty()) {
        int u = pq.top().second;
        int cost = pq.top().first;
        pq.pop();

        if (inMST[u]) continue;

        mstCost += cost;
        inMST[u] = true;

        for (auto& neighbor : adjList[u]) {
            int v = neighbor.first;
            int weight = neighbor.second;

            if (!inMST[v]) {
                pq.push({weight, v});
            }
        }
    }
    return mstCost;
}

// Kruskal's Algorithm
class Edge {
public:
    int u, v, weight;
    Edge(int _u, int _v, int _weight) : u(_u), v(_v), weight(_weight) {}
};

bool compare(Edge e1, Edge e2) {
    return e1.weight < e2.weight;
}

int kruskalMST(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end(), compare);
    UnionFind uf(n);
    int mstCost = 0;

    for (auto& edge : edges) {
        if (uf.find(edge.u) != uf.find(edge.v)) {
            mstCost += edge.weight;
            uf.unionSets(edge.u, edge.v);
        }
    }
    return mstCost;
}

Practice Problems:

  1. LeetCode 1584: Min Cost to Connect All Points
  2. LeetCode 1135: Connecting Cities With Minimum Cost
  3. LeetCode 1631: Path With Minimum Effort (Can be solved with MST)
  4. LeetCode 1101: The Earliest Moment When Everyone Become Friends
  5. LeetCode 1579: Remove Max Number of Edges to Keep Graph Fully Traversable

Cycle Detection

1. Undirected Graph

2. Directed Graph

C++ Code:

#include <iostream>#include <vector>using namespace std;

// Cycle Detection in Undirected Graph using DFS
bool isCyclicDFS(int node, int parent, vector<vector<int>>& adjList, vector<bool>& visited) {
    visited[node] = true;

    for (int neighbor : adjList[node]) {
        if (!visited[neighbor]) {
            if (isCyclicDFS(neighbor, node, adjList, visited)) {
                return true;
            }
        } else if (neighbor != parent) {
            return true;
        }
    }
    return false;
}

bool hasCycleUndirected(int n, vector<vector<int>>& adjList) {
    vector<bool> visited(n, false);

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            if (isCyclicDFS(i, -1, adjList, visited)) {
                return true;
            }
        }
    }
    return false;
}

// Cycle Detection in Directed Graph using DFS
bool isCyclicDFSDirected(int node, vector<vector<int>>& adjList, vector<bool>& visited, vector<bool>& recStack) {
    visited[node] = true;
    recStack[node] = true;

    for (int neighbor : adjList[node]) {
        if (!visited[neighbor] && isCyclicDFSDirected(neighbor, adjList, visited, recStack)) {
            return true;
        } else if (recStack[neighbor]) {
            return true;
        }
    }
    recStack[node] = false;
    return false;
}

bool hasCycleDirected(int n, vector<vector<int>>& adjList) {
    vector<bool> visited(n, false);
    vector<bool> recStack(n, false);

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            if (isCyclicDFSDirected(i, adjList, visited, recStack)) {
                return true;
            }
        }
    }
    return false;
}

Practice Problems:

  1. LeetCode 785: Is Graph Bipartite?
  2. LeetCode 207: Course Schedule (Directed Graph Cycle Detection)
  3. LeetCode 261: Graph Valid Tree
  4. LeetCode 802: Find Eventual Safe States (Directed Graph Cycle Detection)
  5. LeetCode 1462: Course Schedule IV (Cycle detection in multiple queries)

Bipartite Graph

C++ Code:

#include <iostream>#include <vector>#include <queue>using namespace std;

// Check if Graph is Bipartite using BFS
bool isBipartite(int n, vector<vector<int>>& adjList) {
    vector<int> color(n, -1);

    for (int i = 0; i < n; i++) {
        if (color[i] == -1) {
            queue<int> q;
            q.push(i);
            color[i] = 0;

            while (!q.empty()) {
                int node = q.front();
                q.pop();

                for (int neighbor : adjList[node]) {
                    if

 (color[neighbor] == -1) {
                        color[neighbor] = 1 - color[node];
                        q.push(neighbor);
                    } else if (color[neighbor] == color[node]) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

Practice Problems:

  1. LeetCode 785: Is Graph Bipartite?
  2. LeetCode 886: Possible Bipartition
  3. LeetCode 1034: Coloring A Border
  4. LeetCode 994: Rotting Oranges (BFS based problem)
  5. LeetCode 1091: Shortest Path in Binary Matrix

This theme implements a built-in Jekyll feature, the use of Rouge, for syntax highlighting. It supports more than 100 languages. This example is in C++. All you have to do is wrap your code in markdown code tags:

```c++
code code code
```

int main(int argc, char const \*argv[])
{
    string myString;

    cout << "input a string: ";
    getline(cin, myString);
    int length = myString.length();

    char charArray = new char * [length];

    charArray = myString;
    for(int i = 0; i < length; ++i){
        cout << charArray[i] << " ";
    }

    return 0;
}

For displaying code in a list item, you have to be aware of the indentation, as stated in this Stackoverflow answer. You must indent your code by (3 * bullet_indent_level) spaces. This is because kramdown (the markdown engine used by Jekyll) indentation for the code block in lists is determined by the column number of the first non-space character after the list item marker. For example:

1. We can put fenced code blocks inside nested bullets, too.

   1. Like this:

      ```c
      printf("Hello, World!");
      ```

   2. The key is to indent your fenced block in the same line as the first character of the line.

Which displays:

  1. We can put fenced code blocks inside nested bullets, too.

    1. Like this:

      printf("Hello, World!");

    2. The key is to indent your fenced block in the same line as the first character of the line.

By default, it does not display line numbers. If you want to display line numbers for every code block, you can set kramdown.syntax_highlighter_opts.block.line_numbers to true in your _config.yml file.

If you want to display line numbers for a specific code block, all you have to do is wrap your code in a liquid tag:

{% highlight c++ linenos %}
code code code
{% endhighlight %}

The keyword linenos triggers display of line numbers. Produces something like this:



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

 
int main(int argc, char const \*argv[])
{
string myString;

    cout << "input a string: ";
    getline(cin, myString);
    int length = myString.length();

    char charArray = new char * [length];

    charArray = myString;
    for(int i = 0; i < length; ++i){
        cout << charArray[i] << " ";
    }

    return 0;

}


Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • Need a tree of chars for efficient prefix search? Try Tries!
  • Tree traversals in O(1) space? Let's do Morris Traversals
  • Let's synchronize our threads
  • Binary Tree Introduction and Important Traversals
  • NLP Interview Guide - Key Concepts and Techniques