Graph

图的几个常见的概念： Node, Edge, Directed graph, Undirected graph, Adjacent Matrix and Adjacent List

图遍历算法

BFS

Maintain a FIFO queue, put all traversed nodes that haven't been expanded; Generate a node's neighbor nodes, reach out to its neighboring nodes; Terminate until the queue is empty

public void bfs(Node root){
    if(root == null){
        return;
    }
    Queue<Node> q = new LinkedList<>();
    q.offer(root);
    while(!q.empty()){
        int size = q.size();
        for(int i = 0; i < size; i++){
            Node n = q.poll();
            if(n.left != null){
                q.offer(n.left);
            }
            if(n.right != null){
                q.offer(n.right);
            }
        }
    }
}

Time O(n)
Space O(n)

Determine whether a binary tree is a complete binary tree

直观印象是，一棵complete binary tree是所有的Node都尽量的向左下角靠齐，一旦遇到过null之后，就不可以在遇到任何的数字

因此，思路是设置一个flag，当遇到这个bubble的时候，flag被打开，意味着这之后不可以在遇到任何数字，否则可以继续

public void completeChect(Node root){
    if(root == null){
        return;
    }
    Queue<Node> q = new LinkedList<>();
    boolean flag = False;
    q.offer(root);
    while(!q.isEmpty()){
        int size = q.size();
        for(int i = 0; i < size; i++){
            Node n = q.poll();
            if(!flag){
                if(n.left != null){
                    q.offer(n);
                }else{
                    flag = True;
                }
                if(n.right!= null){
                    q.offer(n);
                }else{
                    flag = True;
                }
            } else{
                if(n.left != null || n.right != null){
                    return False;
                }
            }
            
        }
    }
    return True;
}

Dijkstra Algorithm

Find the shortest path cost from a single node to any other node in that graph. 用到的数据结构是 Priority Queue (Min Heap)

在Priority Queue中，首先把（4，0）Pop出去，然后加入

Node(5, 10) Node(3, 1) Node(6, 1) 按照第二个元素进行min Heapify

Pop Node(6, 1) nothing new is added into

Pop Node(3, 1) 加入 Node(2, 2) Min Heapify

Pop Node(2, 2) 加入 Node(5, 3) Node(1,3)

Until the priorityQueue is Empty or target Node is expanded

DFS

Find All Subsets of a Set {a, b, c}

即，每一层包含存在或者不存在，同时需要一个index对当前所在的层数进行记录

void findAllSet(char[] input, int index, StringBuilder solution){
    if(index == input.length){
        System.out.println(solution);
    }
    // Case1: Append input[index] to Solution
    solution.append(input[index]);
    findAllSet(input, index+1, solution);
    solution.deleteCharAt(input[index]);
    
    // Case2: Don't append input[index] to solution
    findAllSet(input, index+1, solution)
}

Find All Permutation

Given a string with no duplicate letters, how to print all permutation of all strings

void permutation(char[] input, int index){
    if(index == input.length){
        System.out.println(input);
        return;
    }
    for(int i = index; i < input.length; i++){
        swap(input, index, i);
        permutation(input, index+1);
        swap(input, index, i);
    }
}