Types of graphs:

• undirected graphs
• directed graphs
• weighted graphs

Terminologies:

• Vertex
• Edge
• Path
• Path Length
• Cycle
• Nagative Weight Cycle
• Connectivity
• Degree of a Vertex
• In-Degree
• Out-Degree

1 Disjoint Set

1.1 Overview of Disjoint Set

Q: Given the vertices and edges between them, how could we quickly check whether two vertices are connected?

The disjoint set is a data structure(others might refer to it as an algorithm), also known as union-find data structure.

The primary use of disjoint sets is to address the connectivity between the components of a network.

Two important functions of a disjoint set:

• The find function: finds the root node of a given vertex.
• The union function: unions two vertices and makes their root nodes the same.

1.2 Quick Find

#include <iostream>
#include <vector>

class DisjointSet
{
public:
    DisjointSet(int num) : root(num)
    {
        for (int i = 0; i < num; ++i) root[i] = i;
    }
    
    int find(int i)
    {
        return root[i];
    }

    void unionSet(int x, int y)
    {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return;  // already in the same set

        for (int i = 0; i < root.size(); ++i)
        {
            if (root[i] == rootY) root[i] = rootX;  // update all nodes whose root is rootY
        }
    }

    bool connected(int x, int y)
    {
        return find(x) == find(y);
    }
private:
    std::vector<int> root;
};

int main()
{
    std::cout << std::boolalpha;
    DisjointSet ds(10);
    // 1-2-5-6-7 3-8-9 4
    ds.unionSet(1, 2);
    ds.unionSet(2, 5);
    ds.unionSet(5, 6);
    ds.unionSet(6, 7);
    ds.unionSet(3, 8);
    ds.unionSet(8, 9);
    std::cout << ds.connected(1, 5) << std::endl;  // true
    std::cout << ds.connected(5, 7) << std::endl;  // true
    std::cout << ds.connected(4, 9) << std::endl;  // false
    // 1-2-5-6-7 3-8-9-4
    ds.unionSet(9, 4);
    std::cout << ds.connected(4, 9) << std::endl;  // true
}

Time Complexity：

• constructor：O(N)
• find: O(1)
• unionSet: O(N)
• connected: O(1)

Space Complexity: O(N)

NOTE: if there are too many unionSet operations, this implementation can be very slow(example: LeetCode1971). Because it always spend O(n) time on the union operations.

1.3 Quick Union

#include <iostream>
#include <vector>

class DisjointSet
{
public:
    DisjointSet(int num) : root(num)
    {
        for (int i = 0; i < num; ++i) root[i] = i;
    }
    
    int find(int x)
    {
        while (x != root[x]) x = root[x];
        return x;
    }

    void unionSet(int x, int y)
    {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) root[rootY] = rootX;
    }

    bool connected(int x, int y)
    {
        return find(x) == find(y);
    }
private:
    std::vector<int> root;
};

int main()
{
    std::cout << std::boolalpha;
    DisjointSet ds(10);
    // 1-2-5-6-7 3-8-9 4
    ds.unionSet(1, 2);
    ds.unionSet(2, 5);
    ds.unionSet(5, 6);
    ds.unionSet(6, 7);
    ds.unionSet(3, 8);
    ds.unionSet(8, 9);
    std::cout << ds.connected(1, 5) << std::endl;  // true
    std::cout << ds.connected(5, 7) << std::endl;  // true
    std::cout << ds.connected(4, 9) << std::endl;  // false
    // 1-2-5-6-7 3-8-9-4
    ds.unionSet(9, 4);
    std::cout << ds.connected(4, 9) << std::endl;  // true
}

Time Complexity：

• constructor：O(N)
• find: O(N)
• unionSet: O(N)
• connected: O(N)

Space Complexity: O(N)

1.4 Union by Rank(Optimization)

The word rank means ordering by specific criteria. To be specific, the rank refers to the height of each vertex. So when we union two vertices, we choose the root node of the vertex with a larger rank.

#include <iostream>
#include <vector>

class DisjointSet
{
public:
    DisjointSet(int num) : root(num), rank(num)
    {
        for (int i = 0; i < num; ++i)
        {
            root[i] = i;
            rank[i] = 1;
        }
    }

    int find(int x)
    {
        while (x != root[x]) x = root[x];
        return x;
    }

    void unionSet(int x, int y)
    {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                root[rootY] = rootX;
            }
            else if (rank[rootX] < rank[rootY]) {
                root[rootX] = rootY;
            }
            else {
                root[rootY] = rootX;
                rank[rootX] += 1;
            }
        }
    }

    bool connected(int x, int y)
    {
        return find(x) == find(y);
    }
private:
    std::vector<int> root;
    std::vector<int> rank;
};

int main()
{
    std::cout << std::boolalpha;
    DisjointSet ds(10);
    // 1-2-5-6-7 3-8-9 4
    ds.unionSet(1, 2);
    ds.unionSet(2, 5);
    ds.unionSet(5, 6);
    ds.unionSet(6, 7);
    ds.unionSet(3, 8);
    ds.unionSet(8, 9);
    std::cout << ds.connected(1, 5) << std::endl;  // true
    std::cout << ds.connected(5, 7) << std::endl;  // true
    std::cout << ds.connected(4, 9) << std::endl;  // false
    // 1-2-5-6-7 3-8-9-4
    ds.unionSet(9, 4);
    std::cout << ds.connected(4, 9) << std::endl;  // true
}

Time Complexity：

• constructor：O(N)
• find: O(logN)
• unionSet: O(logN)
• connected: O(logN)

Space Complexity: O(N)

NOTE: O(α(N)) is regarded as O(1) on average. α refers to the Inverse Ackermann function.

1.5 Path Compression(Optimization)

Use recursion to update root in find method:

int find(int x)
{
    if (x == root[x]) return x;
    return root[x] = find(root[x]);
}

Time Complexity：

• constructor：O(N)
• find: O(α(N))
• unionSet: O(α(N))
• connected: O(α(N))

Space Complexity: O(N)

NOTE: O(α(N)) is regarded as O(1) on average. α refers to the Inverse Ackermann function.

1.6 Summary

1.7 Exercises

• LeetCode 1971
• LeetCode 547
• LeetCode 261
• LeetCode 323
• LeetCode 1101
• LeetCode 1202
• LeetCode 399(weight)

2 Depth-First Search

2.1 Overview of DFS

Q: Give a graph, how can we find all of its vertices, and how can we find all paths between two vertices?

• BFS can explore all paths from the start vertex to all other vertices. It is mainly used to:
  • Traverse all vertices in a graph
  • Traverse all paths between any two vertics in a graph
• Depth means: going as deep as possible.
• Use Stack
• Traversing all vertices
  • Time Complexity: O(V+E)
  • Space Complexity: O(V)
• Traversing all paths
  • Time Complexity: O((V-1)!)
    • worst case
  • Space Complexity: O(V^3)

Exercises

LeetCode1971: Find if Path Exists in Graph

class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        // DFS
        std::vector<std::vector<int>> graph(n);
        std::vector<bool> seen(n, false);
        for (const auto& edge : edges)
        {
            graph[edge[0]].emplace_back(edge[1]);
            graph[edge[1]].emplace_back(edge[0]);
        }
        std::stack<int> stack;
        stack.push(source);
        while (!stack.empty())
        {
            int curr = stack.top();
            stack.pop();
            if (curr == destination) return true;

            if (seen[curr]) continue;
            seen[curr] = true;

            for (const auto& next : graph[curr]) stack.push(next);
        }

        return false;
    }
};

Others

• LeetCode797
• LeetCode133

3 Breadth-First Search

3.1 Overview of BFS

• traverse all vertices: same as DFS
  • Time Complexity: O(V+E)
  • Space Complexity: O(V)
• advantage: find the shortest path between two vertices in a graph where all edges have euqal and positive weights
  • DFS can also find the shortest path, but it must traverse all paths
  • but BFS can find it whithout traversing all paths, meaning it’s faster for this problem
  • when find a path, it is guaranteed to be the shortest path
  • Time Complexity: O(V+E)
  • Space Complexity: O(V)
• use a queue

Excercise

LeetCode1971: Find if Path Exists in Graph

class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        // BFS
        std::vector<std::vector<int>> graph(n);
        std::vector<bool> seen(n, false);
        for (const auto& edge : edges)
        {
            graph[edge[0]].emplace_back(edge[1]);
            graph[edge[1]].emplace_back(edge[0]);
        }
        std::queue<int> queue;
        queue.push(source);
        while (!queue.empty())
        {
            int curr = queue.front();
            queue.pop();
            if (curr == destination) return true;

            if (seen[curr]) continue;
            seen[curr] = true;

            for (const auto& next : graph[curr]) queue.push(next);
        }

        return false;
    }
};

Others

References

• Overview of Disjoint Set
• Quick Find – Disjoint Set
• Quick Union – Disjoint Set
• Union by Rank – Disjoint Set
• Path Compression Optimization
• 花花酱 Disjoint-set/Union-find Forest
• Overview of Depth-First Search Algorithm
• Traversing all Vertices – Depth-First Search Algorithm
• Traversing all paths between two vertices – Depth-First Search Algorithm
• Can a backtracking tail recursive algorithm be converted to iteration?
• Overview of Breadth-First Search Algorithm