Algorithm ladder VI -- more BT/B

references: Geeks for geeks https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/
topics: graph -- introduction, dfs, bfs.
extra: leetcode 127. Word Ladder,

Geeks for Geeks

image.png

126 word ladder <-> done
127 word ladder II <-> to be done
103 BT zigzag level order traversal
133 clone graph
199 BT right side view <-> done
200 number of island

Graphs and its representation

Representations:

1. Adjacency Matrix:

adj[i][j] = w <--> (1) edge: i->j (2) weight: w
pros: easy to implement; easy to query
cons: O(V^2) space.

2. Adjacency List
3. Incidence matrix/incidence list

Breadth First Traversal for a Graph

要点： graph中可能有cycle。在tree的BFS基础上还需要一个boolean array visited。每一次只把visited==false的node加入队列中。
application of BFS

image.png

Depth first Search for a graph

Applications of Depth First Search

image.png

strongly connected component
(i) undirected graph: dfs/ union-find
(ii) direccted graph: kasaraju's algorith https://www.geeksforgeeks.org/find-a-mother-vertex-in-a-graph/
一次postorder sort，得到kernal DAG; 再一次按照postorder dfs reversedGraph，得到strongly connected component

leetcode 127 word ladder

image.png

public class WordLadder {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            Set<String> marked = new HashSet<>();
            Queue<String> queue = new LinkedList<String>();
            queue.offer(beginWord); 
            marked.add(beginWord);
            
            int layer = 1;
            int layerSize = 1;
            while (!queue.isEmpty()) {
                String cur = queue.poll(); 
                if (cur.equals(endWord)) 
                    return layer;
                layerSize--;
                
                //找cur的所有adjacent nodes
                for (String s : wordList) {
                    if (isAdjacent(cur, s)) {
                        if (!marked.contains(s)) {
                            marked.add(s);
                            queue.offer(s);
                        }
                    }
                }
                
                if (layerSize == 0) {
                    layerSize = queue.size();
                    layer++;
                }
            }
            
            // if not found;
        return 0;
    }
    
    private boolean isAdjacent(String a, String b) {
            if (a == null || b == null || a.length() != b.length()) return false;
            int diff = 0;
            for (int i = 0; i < a.length(); i++) {
                if (a.charAt(i) != b.charAt(i)) {
                    diff++;
                }
            }
            return diff == 1 ? true : false;
    }
}

解析：
等同于再一个无向图中做BFS，起点是beginWord，终点是endWord
比较简单的想法是先根据wordlist构建无向图，再进行常规的bfs搜索。
快一些的方法是不够造无向图，每一步直接搜索adjcent nodes

leetcode 126 Word ladder II

image.png

这题比127 word ladder难在：

1. 需要求所有shortest paths
2. 需要有具体的path

two phase solution:
phase I: bfs 求出具体的最短路径minDist。
phase II: dfs 遍历所有路径长为minDist(非常像穷举法)，遇到结尾为endWord的就输出路径。

199 Binary tree right side view

image.png

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if (root == null) 
                return res;
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int layerSize = 1;
        
        while (!queue.isEmpty()) {
                TreeNode cur = queue.poll();
                layerSize--;
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                    
                if (cur.right != null) {
                    queue.offer(cur.right);
                }

                if (layerSize == 0) {
                    layerSize = queue.size();
                    res.add(cur.val);
                }
        }
        return res;
    }

解释：bfs输出每一个layer的最后一个元素就是rightside view

133 Clone Graph

image.png

     public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
            if (node == null) 
                return null;
        
        // phase I 
            Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
            Set<UndirectedGraphNode> marked = new HashSet<>();
            Queue<UndirectedGraphNode> queue = new LinkedList<>();
            queue.offer(node);
            marked.add(node);
            while (!queue.isEmpty()) {
                UndirectedGraphNode curNode = queue.poll();
                map.put(curNode, new UndirectedGraphNode(curNode.label)); // copy node;
                
                for (UndirectedGraphNode n : curNode.neighbors) {
                    if (!marked.contains(n)) {
                        marked.add(n);
                        queue.offer(n);
                    }
                }
            }       
            
            // phase II copy edges;
            marked.clear();
            queue.offer(node);
            marked.add(node);
            while (!queue.isEmpty()) {
                UndirectedGraphNode curNode = queue.poll();
                UndirectedGraphNode curNodeCopy = map.get(curNode);
                
                for (UndirectedGraphNode n : curNode.neighbors) {
                    curNodeCopy.neighbors.add(map.get(n));
                    if (!marked.contains(n)) {
                        marked.add(n);
                        queue.offer(n);
                    }
                }
            }           
            return map.get(node);
    }

解释: two phases:

1. dfs/bfs copy nodes; O(V+E)
2. dfs/bfs copy edges; O(V+E)