LeetCode Problem: Graph Topics

1. Clone Graph

Given a reference of a node in a connected undirected graph. Return a deep copy (clone) of the graph. To solve the problem, we use:

1. a queue to do the breadth-first search
2. a map to do the copy

Here is the code:

import java.util.*;

public class CloneGraph {
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        Queue<Node> queue = new LinkedList<>();
        Map<Node, Node> map = new HashMap<>();
        queue.add(node);
        map.put(node, null);

        while (!queue.isEmpty()) {
            Node currentNode = queue.remove();
            Node copyNode = new Node(currentNode.val);
            map.put(currentNode, copyNode);

            for (Node neighbour : currentNode.neighbors) {
                if (!map.containsKey(neighbour)) {
                    queue.add(neighbour);
                    map.put(neighbour, null);
                }
            }
        }

        for (Node original : map.keySet()) {
            Node copy = map.get(original);
            for (Node neighbour : original.neighbors) {
                copy.neighbors.add(map.get(neighbour));
            }
        }
        return map.get(node);
    }
}

class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

The process of the above code is like this:

---

2. Possible Bipartition

Given a set of N people (numbered 1, 2, …, N), we would like to split everyone into two groups of any size. Each person may dislike some other people, and they should not go into the same group. Formally, if dislikes[i] = [a, b], it means it is not allowed to put the people numbered a and b into the same group. Return true if and only if it is possible to split everyone into two groups in this way.

Example 1:
Input: N = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4], group2 [2,3]

Example 2:
Input: N = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false

Example 3:
Input: N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: false

Firstly we should understand what is a bipartite graph. We use graph coloring to check whether a graph is bipartite or not:

Color a node as red, and all its neighbours as green recursively. If there is any conflicts then the graph is not bipartite.

In another word, for a bipartite graph, every single node has neighbours with different color. For example, suppose we have a graph like this:

And we can use DFS or BFS to color this graph. Here we use DFS:

After coloring the graph, we can find that each node has several different-colored neighbours. Therefore it is a bipartite graph, and we can seperate the nodes into two groups:

In another example, after coloring the graph we find it is not a bipartite graph:

Here is the code to solve the possible bipartition problem:

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class PossibleBipartition {

    public boolean possibleBipartition(int N, int[][] dislikes) {
        // 1. build the graph
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        for (int[] dislike : dislikes) {
            int a = dislike[0];
            int b = dislike[1];
            graph.putIfAbsent(a, new HashSet<>());
            graph.putIfAbsent(b, new HashSet<>());
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        // 2. graph coloring
        int[] colors = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            if (colors[i] == 0 && !dfs(graph, colors, i, 1)) {// color == 0 means that it has not been colored yet.
                return false;
            }
        }

        return true;
    }

    public boolean dfs(Map<Integer, Set<Integer>> graph, int[] colors, int node, int color) {
        if(colors[node] != 0) {// node has been colored
            return colors[node] == color;
        }

        colors[node] = color;
        if(graph.get(node) == null) {
            return true;
        }

        for(int next: graph.get(node)){
            if(!dfs(graph, colors, next, -color)) {
                return false;
            }
        }

        return true;
    }
}

The process of above code is like this:

---