Graph Problems and Terminology

Here's a friendly overview of common graph problems, categorized by different aspects of graph terminology:

Traversal Problems

• Breadth-First Search (BFS):
  • Find the shortest path in an unweighted graph.
  • Level-order traversal in trees.
• Depth-First Search (DFS):
  • Find connected components in a graph.
  • Detect cycles in a graph.
  • Topological sorting of a Directed Acyclic Graph (DAG).

Shortest Path Problems

• Dijkstra's Algorithm:
  • Find the shortest path from a source vertex to all other vertices in a weighted graph with non-negative weights.
• Bellman-Ford Algorithm:
  • Find the shortest path from a source vertex to all other vertices in a graph that may have negative weights.
• Floyd-Warshall Algorithm:
  • Find shortest paths between all pairs of vertices in a weighted graph.
• A* Algorithm:
  • Find the shortest path in a weighted graph using heuristics (used in pathfinding algorithms).

Minimum Spanning Tree (MST) Problems

• Kruskal’s Algorithm:
  • Find the Minimum Spanning Tree (MST) of a graph using a union-find data structure.
• Prim’s Algorithm:
  • Find the MST by growing the tree from an initial vertex using a priority queue.

Cycle Detection Problems

• Cycle Detection in Directed Graphs:
  • Use DFS to detect cycles in a directed graph (e.g., to check if a graph is a DAG).
• Cycle Detection in Undirected Graphs:
  • Use union-find data structure to detect cycles in an undirected graph.

Connectivity Problems

• Connected Components:
  • Find all connected components in an undirected graph.
• Articulation Points:
  • Find vertices whose removal increases the number of connected components.
• Bridges:
  • Find edges whose removal increases the number of connected components.

Topological Sorting

• Topological Sorting:
  • Order vertices in a Directed Acyclic Graph (DAG) such that for every directed edge (u, v), vertex u comes before v.

Graph Coloring

• Graph Coloring:
  • Assign colors to vertices of a graph such that no two adjacent vertices share the same color (used in scheduling problems).
• Chromatic Number:
  • Determine the minimum number of colors needed to color a graph.

Flow Problems

• Maximum Flow:
  • Find the maximum flow from a source to a sink in a flow network (using algorithms like Ford-Fulkerson, Edmonds-Karp).
• Minimum Cut:
  • Find the smallest cut (set of edges) that separates the source and sink in a flow network.

Matching Problems

• Maximum Bipartite Matching:
  • Find the maximum matching in a bipartite graph (e.g., job assignment problems).
• Hungarian Algorithm:
  • Solve the assignment problem where each task is assigned to exactly one worker to minimize cost.

Distance Problems

• Diameter of a Graph:
  • Find the longest shortest path between any pair of vertices in a graph.
• K-Shortest Paths:
  • Find multiple shortest paths between two vertices in a weighted graph.

These problems cover a broad spectrum of graph theory and are commonly encountered in various domains, including computer science, operations research, and optimization.

Understanding Key Graph Terminology

Let’s explore some essential graph terminology to get a solid grasp of the basics:

1. Vertex (Node)

Definition: A fundamental unit of a graph, representing an entity or a point.

Example: In a social network, a person can be represented as a vertex.

2. Edge (Link)

Definition: A connection between two vertices, which can be directed or undirected.

Example: In a social network, a friendship between two people is represented as an edge.

3. Adjacency

Definition: Two vertices are adjacent if there is an edge connecting them.

Example: If there's a direct connection (edge) between vertices A and B, A and B are considered adjacent.

4. Graph

Definition: A collection of vertices and edges. Graphs can be categorized based on their properties.

Example: A social network graph where vertices represent people and edges represent friendships.

5. Directed Graph (Digraph)

Definition: A graph where edges have a direction, going from one vertex to another.

Example: A workflow with tasks where some tasks need to be completed before others.

6. Undirected Graph

Definition: A graph where edges have no direction, making the connection between vertices bidirectional.

Example: An undirected social network where friendships are mutual.

7. Weighted Graph

Definition: A graph where edges have weights, representing costs, distances, or other metrics.

Example: A road network where edges represent distances between cities.

8. Unweighted Graph

Definition: A graph where edges have no weights or all edges are considered to have the same weight (typically 1).

Example: A simple social network where all connections are equal.

9. Path

Definition: A sequence of vertices connected by edges.

Example: In a city map, a path could represent the route from one location to another.

10. Cycle

Definition: A path that starts and ends at the same vertex, without repeating any other vertices or edges.

Example: A route that forms a loop in a city.

11. Connected Graph

Definition: A graph in which there is a path between every pair of vertices.

Example: A network of computers where every computer can communicate with every other computer.

12. Disconnected Graph

Definition: A graph where some vertices are not connected by any path.

Example: A set of isolated networks that do not communicate with each other.

13. Subgraph

Definition: A portion of a graph formed from a subset of its vertices and edges.

Example: A section of a social network graph focusing on a particular community.

14. Tree

Definition: A connected acyclic graph.

Example: A hierarchical organization chart.

15. Forest

Definition: A disjoint set of trees (i.e., a collection of trees).

Example: Multiple organizational charts that do not share any common vertices.

16. Degree of a Vertex

Definition: The number of edges incident to a vertex.

Example: In a social network, the degree of a person could represent their number of friends.

17. Indegree and Outdegree

Definition: In a directed graph, the indegree is the number of incoming edges to a vertex, and the outdegree is the number of outgoing edges from a vertex.

Example: In a citation graph, the indegree could represent how many times a paper has been cited, and the outdegree represents how many papers it cites.

These terms provide a solid foundation for understanding and solving graph-related problems. Happy learning!

Vertical Order Traversal of a Binary Tree

Given the root of a binary tree, calculate the vertical order traversal of the binary tree. For each node at position (row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0). The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values. Return the vertical order traversal of the binary tree.

Approach 1:

class Tuple {
    public Tuple(TreeNode x, int row, int col) {
        this.x = x;
        this.row = row;
        this.col = col;
    }

    TreeNode x;
    int row;
    int col;
}

class Solution {
    public List> verticalTraversal(TreeNode root) {
        List> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

        TreeMap>> t = new TreeMap<>();
        Queue q = new LinkedList<>();
        q.add(new Tuple(root, 0, 0));

        while (!q.isEmpty()) {
            Tuple temp = q.poll();
            TreeNode p = temp.x;
            int x_row = temp.row;
            int y_col = temp.col;

            t.putIfAbsent(x_row, new TreeMap<>());
            t.get(x_row).putIfAbsent(y_col, new PriorityQueue<>());
            t.get(x_row).get(y_col).offer(p.val);

            if (p.left != null) {
                q.add(new Tuple(p.left, x_row - 1, y_col + 1));
            }
            if (p.right != null) {
                q.add(new Tuple(p.right, x_row + 1, y_col + 1));
            }
        }

        for (TreeMap> ys : t.values()) {
            List column = new ArrayList<>();
            for (PriorityQueue nodes : ys.values()) {
                while (!nodes.isEmpty()) {
                    column.add(nodes.poll());
                }
            }
            ans.add(column);
        }

        return ans;
    }
}
                

Time Complexity: O(n) and Space Complexity: O(n)

Find a Corresponding Node of a Binary Tree in a Clone of That Tree

Given two binary trees original and cloned and given a reference to a node target in the original tree. The cloned tree is a copy of the original tree. Return a reference to the same node in the cloned tree. Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.

Approach 1: DFS: Recursive Inorder Traversal.

class Solution {
    TreeNode ans, target;
    
    public void inorder(TreeNode o, TreeNode c) {
        if (o != null) {
            inorder(o.left, c.left);
            if (o == target) {
                ans = c;    
            }
            inorder(o.right, c.right);    
        }
    }
    
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        this.target = target;
        inorder(original, cloned);
        return ans;
    }
}
                

Time Complexity: O(n) and Space Complexity: O(n)

All Nodes Distance K in Binary Tree

Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node. You can return the answer in any order.

Approach 1:

class Solution {
    Map> graph;
    List answer;
    Set visited;

    public List distanceK(TreeNode root, TreeNode target, int k) {
        graph = new HashMap<>();
        buildGraph(root, null);

        answer = new ArrayList<>();
        visited = new HashSet<>();
        visited.add(target.val);

        dfs(target.val, 0, k);

        return answer;
    }

    // Recursively build the undirected graph from the given binary tree.
    private void buildGraph(TreeNode cur, TreeNode parent) {
        if (cur != null && parent != null) {
            graph.computeIfAbsent(cur.val, k -> new ArrayList<>()).add(parent.val);
            graph.computeIfAbsent(parent.val, k -> new ArrayList<>()).add(cur.val);
        }
        if (cur.left != null) {
            buildGraph(cur.left, cur);
        }
        if (cur.right != null) {
            buildGraph(cur.right, cur);
        }
    }

    private void dfs(int cur, int distance, int k) {
        if (distance == k) {
            answer.add(cur);
            return;
        }
        for (int neighbor : graph.getOrDefault(cur, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                dfs(neighbor, distance + 1, k);
            }
        }
    }
}
                

Time Complexity: O(n) and Space Complexity: O(n)

Smallest Subtree with all the Deepest Nodes

Given the root of a binary tree, the depth of each node is the shortest distance to the root. Return the smallest subtree such that it contains all the deepest nodes in the original tree. A node is called the deepest if it has the largest depth possible among any node in the entire tree. The subtree of a node is a tree consisting of that node, plus the set of all descendants of that node.

Approach 1: Paint Deepest Nodes

class Solution {
    Map depth;
    int max_depth;
    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        depth = new HashMap();
        depth.put(null, -1);
        dfs(root, null);
        max_depth = -1;
        for (Integer d: depth.values())
            max_depth = Math.max(max_depth, d);

        return answer(root);
    }

    public void dfs(TreeNode node, TreeNode parent) {
        if (node != null) {
            depth.put(node, depth.get(parent) + 1);
            dfs(node.left, node);
            dfs(node.right, node);
        }
    }

    public TreeNode answer(TreeNode node) {
        if (node == null || depth.get(node) == max_depth)
            return node;
        TreeNode L = answer(node.left),
                    R = answer(node.right);
        if (L != null && R != null) return node;
        if (L != null) return L;
        if (R != null) return R;
        return null;
    }
}
                

Time Complexity: O(n) and Space Complexity: O(n)

Number of Good Leaf Nodes Pairs

You are given the root of a binary tree and an integer distance. A pair of two different leaf nodes of a binary tree is said to be good if the length of the shortest path between them is less than or equal to distance. Return the number of good leaf node pairs in the tree.

Approach 1: Graph Conversion + BFS

class Solution {

    public int countPairs(TreeNode root, int distance) {
        Map> graph = new HashMap<>();
        Set leafNodes = new HashSet<>();

        traverseTree(root, null, graph, leafNodes);

        int ans = 0;

        for (TreeNode leaf : leafNodes) {
            Queue bfsQueue = new LinkedList<>();
            Set seen = new HashSet<>();
            bfsQueue.add(leaf);
            seen.add(leaf);
            // Go through all nodes that are within the given distance of
            // the current leaf node
            for (int i = 0; i <= distance; i++) {
                // Clear all nodes in the queue (distance i away from leaf node)
                // Add the nodes' neighbors (distance i+1 away from leaf node)
                int size = bfsQueue.size();
                for (int j = 0; j < size; j++) {
                    // If current node is a new leaf node, add the found pair to our count
                    TreeNode currNode = bfsQueue.remove();
                    if (leafNodes.contains(currNode) && currNode != leaf) {
                        ans++;
                    }
                    if (graph.containsKey(currNode)) {
                        for (TreeNode neighbor : graph.get(currNode)) {
                            if (!seen.contains(neighbor)) {
                                bfsQueue.add(neighbor);
                                seen.add(neighbor);
                            }
                        }
                    }
                }
            }
        }
        return ans / 2;
    }

    private void traverseTree(
        TreeNode currNode,
        TreeNode prevNode,
        Map> graph,
        Set leafNodes
    ) {
        if (currNode == null) {
            return;
        }
        if (currNode.left == null && currNode.right == null) {
            leafNodes.add(currNode);
        }
        if (prevNode != null) {
            graph.computeIfAbsent(prevNode, k -> new ArrayList());
            graph.get(prevNode).add(currNode);
            graph.computeIfAbsent(currNode, k -> new ArrayList());
            graph.get(currNode).add(prevNode);
        }
        traverseTree(currNode.left, currNode, graph, leafNodes);
        traverseTree(currNode.right, currNode, graph, leafNodes);
    }
}
                

Time Complexity: O(n^2) and Space Complexity: O(n)