Find the Connected Component in the Undirected Graph

Find the Connected Component in the Undirected Graph

Find the number connected component in the undirected graph. Each node in the graph contains a label and a list of its neighbors. (a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.)

Example

Given graph:

A------B  C
 \     |  | 
  \    |  |
   \   |  |
    \  |  |
      D   E

Return {A,B,D}, {C,E}. Since there are two connected component which is {A,B,D}, {C,E}

Solution: BFS

public List<List<Integer>> connectedSet(ArrayList<UndirectedGraphNode> nodes) {
    List<List<Integer>> result = new ArrayList<>();
    if (nodes == null || nodes.size() == 0) {
        return result;
    }
    Queue<UndirectedGraphNode> q = new LinkedList<>();
    q.offer(nodes.get(0));
    List<Integer> component = new ArrayList<>();
    Set<UndirectedGraphNode> visited = new HashSet<>();
    while (!nodes.isEmpty()) {
        if (q.isEmpty()) {
            Collections.sort(component);
            result.add(new ArrayList<>(component));
            q.offer(nodes.get(0));
            component = new ArrayList<>();
        } else {
            UndirectedGraphNode curr = q.poll();
            if (!visited.contains(curr)) {
                visited.add(curr);
                nodes.remove(curr);
                component.add(curr.label);
                for (UndirectedGraphNode neighbor : curr.neighbors) {
                    q.offer(neighbor);
                }
            }
        }
    }
    if (!component.isEmpty()) {
        result.add(component);
    }
    return result;
}
FacebookTwitterGoogle+Share

Word Ladder I && II

Word Ladder I  — 只需要找一条最短路

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary

Example

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

Solution: BFS – BFS模板 O(n*L) n: size of dict, L: the max length of the words

visited set记录已经访问过的路 一旦找到一条就退出

注意字符串的处理

public int ladderLength(String start, String end, Set<String> dict) {
    if (dict == null || dict.size() == 0) {
        return 0;
    }
    Queue<String> queue = new LinkedList<String>();
    queue.offer(start);
    int length = 1;
    Set<String> visited = new HashSet<>();
    visited.add(start);
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            String curr = queue.poll();
            for (char newChar = 'a'; newChar <= 'z'; newChar++) {
                for (int j = 0; j < start.length(); j++) {
                    if (newChar == curr.charAt(j)) {
                        continue;
                    }
                    String nextStep = curr.substring(0, j) + newChar + curr.substring(j + 1);
                    if (nextStep.equals(end)) {
                        return length + 1;
                    }
                    if (dict.contains(nextStep) && !visited.contains(nextStep)) {
                        queue.offer(nextStep);
                        visited.add(nextStep);
                    }
                }
            }
        }
        length++;
    }
    return 0;
}

Word Ladder II –找出所有最短路

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary
Example

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]
Note

  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

Solution: BFS+DFS

1. 先用BFS找出最短路径的长度,同时把相邻节点和每个点到起点的distance保存下来

2. 用DFS找出所有最短路径,distance超过最短路径的长度的就不用考虑了,所谓pruning.

public List<List<String>> findLadders(String start, String end, Set<String> dict) {
    List<List<String>> result = new ArrayList<>();
    if (dict == null || dict.size() == 0) {
        return result;
    }
    List<String> curr = new ArrayList<>();
    curr.add(start);
    Map<String, Integer> distance = new HashMap<>();
    Map<String, List<String>> neighborsMap = new HashMap<>();
    int minTrans = bfs(start, end, dict, distance, neighborsMap);
    findLaddersHelper(curr, end, minTrans, distance, neighborsMap, result);
    return result;
}

public void findLaddersHelper(List<String> curr, String end, int maxStep, Map<String, Integer> distance,
                              Map<String, List<String>> neighborsMap, List<List<String>> result) {
    String currStr = curr.get(curr.size() - 1);
    if (maxStep == 0) {
        if (currStr.equals(end)) {
            result.add(new ArrayList<>(curr));
        }
        return;
    }
    for (String neighbor : neighborsMap.get(currStr)) {
        if (distance.get(neighbor) == distance.get(currStr) + 1) {
            curr.add(neighbor);
            findLaddersHelper(curr, end, maxStep - 1, distance, neighborsMap, result);
            curr.remove(curr.size() - 1);
        }
    }
}

//first use BFS to find the shortest transformation
public int bfs(String start, String end, Set<String> dict,
               Map<String, Integer> distance, Map<String, List<String>> neighborsMap) {
    Queue<String> queue = new LinkedList<>();
    queue.offer(start);
    distance.put(start, 0);
    int minTrans = -1;
    while (!queue.isEmpty()) {
        int size = queue.size();
        String str = queue.poll();
        List<String> neighbors = new ArrayList<>();
        for (char newChar = 'a'; newChar <= 'z'; newChar++) {
            for (int index = 0; index < start.length(); index++) {
                if (newChar == str.charAt(index)) {
                    continue;
                }
                String newStr = str.substring(0, index) + newChar + str.substring(index + 1);
                if (newStr.equals(end) && minTrans == -1) {
                    minTrans = distance.get(str) + 1;
                }
                if (dict.contains(newStr)) {
                    neighbors.add(newStr);
                    if (!distance.containsKey(newStr)) {
                        distance.put(newStr, distance.get(str) + 1);
                        queue.offer(newStr);
                    }
                }
            }
        }
        neighborsMap.put(str, neighbors);
    }
    return minTrans;
}

Topological Sorting

Topological Sorting

Given an directed graph, a topological order of the graph nodes is defined as follow:

  • For each directed edge A -> B in graph, A must before B in the order list.
  • The first node in the order can be any node in the graph with no nodes direct to it.

Find any topological order for the given graph.

Example

For graph as follow:

picture

The topological order can be:

<code>[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]
...
</code>
Note

You can assume that there is at least one topological order in the graph.

Challenge

Can you do it in both BFS and DFS?

Solution 1. BFS

1. first create a map which contains all the nodes and its indegrees

2. only add node with 0 indegree to the list and once the node is select, remove 1 indegree from all its neighbors

public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
    //BFS
    ArrayList<DirectedGraphNode> result = new ArrayList<>();
    if (graph == null || graph.size() <= 1) {
        return graph;
    }
    HashMap<DirectedGraphNode, Integer> inDegreeMap = new HashMap<>();
    for (DirectedGraphNode node : graph) {
        if (!inDegreeMap.containsKey(node)) {
            inDegreeMap.put(node, 0);
        }
        for (DirectedGraphNode neighbor : node.neighbors) {
            if (inDegreeMap.containsKey(neighbor)) {
                inDegreeMap.put(neighbor, inDegreeMap.get(neighbor) + 1);
            } else {
                inDegreeMap.put(neighbor, 1);
            }
        }
    }
    while (!inDegreeMap.isEmpty()) {
        for (DirectedGraphNode node : inDegreeMap.keySet()) {
            if (inDegreeMap.get(node) == 0) {
                result.add(node);
                inDegreeMap.remove(node);
                for (DirectedGraphNode neighbor : node.neighbors) {
                    inDegreeMap.put(neighbor, inDegreeMap.get(neighbor) - 1);
                }
                break;
            }
        }
    }
    return result;
}

Clone Graph

Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
OJ’s undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

  1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
  2. Second node is labeled as 1. Connect node 1 to node 2.
  3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Solution: BFS遍历图 用Hash表存储Original Node-》 Copy Node 映射
O(n) time complexity, O(n) space

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if (node == null) {
        return null;
    }
    Queue<UndirectedGraphNode> queue = new LinkedList<>();
    Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
    queue.offer(node);
    UndirectedGraphNode copyRoot = new UndirectedGraphNode(node.label);
    map.put(node, copyRoot);
    while (!queue.isEmpty()) {
        int count = queue.size();
        for (int i = 0; i < count; i++) {
            UndirectedGraphNode curr = queue.poll();
            for (UndirectedGraphNode neighbor : curr.neighbors) {
                if (!map.containsKey(neighbor)) {
                    queue.offer(neighbor);
                    UndirectedGraphNode currCopy = new UndirectedGraphNode(neighbor.label);
                    map.put(neighbor, currCopy);
                }
            }
        }
    }
    for (UndirectedGraphNode originalNode : map.keySet()) {
        for (UndirectedGraphNode neighbor : originalNode.neighbors) {
            map.get(originalNode).neighbors.add(map.get(neighbor));
        }
    }
    return map.get(node);
}