Interview Note - Graph & Search

Clone Graph

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     ArrayList<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node == null) {
            return null;
        }

        LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
        HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
        queue.offer(node);
        map.put(node, new UndirectedGraphNode(node.label));

        while(!queue.isEmpty()) {
            UndirectedGraphNode cur = queue.poll();
            for(int i = 0; i < cur.neighbors.size(); i++) {
                // !!! if node not in map, add a new node into the map !!!
                if(!map.containsKey(cur.neighbors.get(i))) {
                    map.put(cur.neighbors.get(i), new UndirectedGraphNode(cur.neighbors.get(i).label));
                    queue.offer(cur.neighbors.get(i));
                }
                // now we are sure that the node is existed, add the neighbors to the value
                map.get(cur).neighbors.add(map.get(cur.neighbors.get(i)));
            }
        }

        return map.get(node);
    }
}

Topological Sorting
DFS: O(n) time with O(n) space for the map and the result.

/**
 * Definition for Directed graph.
 * class DirectedGraphNode {
 *     int label;
 *     ArrayList<DirectedGraphNode> neighbors;
 *     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
 * };
 */
public class Solution {
    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */    
    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        ArrayList<DirectedGraphNode> result = new ArrayList<DirectedGraphNode>();
        if(graph == null || graph.size() == 0) {
            return result;
        }
        // construct map with all nodes
        HashMap<DirectedGraphNode, Integer> map = new HashMap<DirectedGraphNode, Integer>();
        for(DirectedGraphNode node: graph) {
            // mark 0 as unsorted
            map.put(node, 0);
        }
        // find a new unsorted node to start sorting (if possible):
        while (hasUnsorted(map, graph)) {
            DirectedGraphNode node = null;
            for (DirectedGraphNode temp : graph) {
                if (map.get(temp) == 0) {
                    node = temp;
                }
            }
            // get the node and do sort(search):
            sort(map, graph, result, node);
        }
        return result;
    }
    
    // check if there is any node that not yet been sorted
    public boolean hasUnsorted(Map<DirectedGraphNode, Integer> map, ArrayList<DirectedGraphNode> graph){
        for (DirectedGraphNode node : graph) {
            if (map.get(node) == 0) {
                return true;
            }
        }
        return false;
    }
    
    // search and sort the graph
    public void sort(Map<DirectedGraphNode, Integer> map, ArrayList<DirectedGraphNode> graph, ArrayList<DirectedGraphNode> result, DirectedGraphNode node){
        if (map.get(node) != 0) {
            // if 1: System.out.println("It is not a DAG");
            // if 2: sorted
            return;
        }
        // mark 1 as visited(not yet been sorted), do with its neighbors:
        map.put(node, 1);
        for (DirectedGraphNode next : node.neighbors) {
            sort(map, graph, result, next);
        }
        // mark 2 as sorted
        // map.put(node, 2);
        result.add(0, node);
    }
}

Read More