001圖相關的術語有哪些？

圖(Graph)：是一種復雜的非線性表結構。
頂點：圖中的元素我們叫做頂點(vertex)。
邊：圖中的一個頂點可以與任意其他頂點建立連接關系。我們把這種建立的關系叫做邊(edge)。
度：跟頂點相連接的邊的條數叫做度(degree)。
出度：指向別人的數量。
入度: 指向自己的數量。
有向圖：邊有方向的圖，比如A點到B點的直線距離，微信的添加好友是雙向的
無向圖：邊無方向的圖，當然無向圖可以理解成特殊的有向圖。

帶權圖:在帶權圖中，每條邊都有一個權重(weight)，我們可以通過這個權重 來表示 一些可度量的值。

002什么是圖的鄰接矩陣(Adjacency Matrix)？

鄰接矩陣的本質是二維數組，∞表示沒有連線，1 表示有連線。
1. 通過二維數組，我們可以很快的找到一個頂點和哪些頂點有連線。（比如 A頂點,只需要 遍歷第一行即可）
2. 另外，A - A，B - B（也就是頂點到自己的連線），通常使用∞表示。

003鄰接矩陣的問題？

1)如果是一個無向圖，鄰接矩陣展示出來的二維數組，其實是一個對稱圖。也就是 A -> D 是 1 的時候，對稱的位置 D -> 1 一定也是 1。那么這種情況下會造成空間的浪費。
2)鄰接矩陣還有一個比較嚴重的問題就是如果圖是一個稀疏圖，如果矩陣中將存在大量的∞，這意味著我們浪費了計算機存儲空間來表示根本不存在的邊。而且即使只有一個邊，我們也必須遍歷一行來找出這個邊，也浪費很多時間。

004什么是圖的鄰接表？

鄰接表由圖中每個頂點以及和頂點相鄰的頂點列表組成。這個列表有很多中方式來存儲：數組/鏈表/字典(哈希表)都可以。比如我們要表示和 A 頂點有關聯的頂點（邊），A 和 B/C/D 有邊，那么我們可以通過 A 找到 對應的數組/鏈表/字典，再取出其中的內容就可以了。

005圖的鄰接表問題？

鄰接表計算“出度”是比較簡單的（出度：指向別人的數量, 入度: 指向自己的數量），計算有向圖的“入度”，那么是一件非常麻煩的事情。

006如何來封裝一個圖？

封裝圖中的節點類，屬性包括節點對應的值value，收斂進來的節點個數in，發散出去的節點個數out,從該節點發散出去并直接相連的節點nexts，該節點包含的邊數edges;

public class Node {
    public int value;
    public int in;
    public int out;
    public ArrayList<Node> nexts;
    public ArrayList<Edge> edges;

    public Node(int value) {
        this.value = value;
        in = 0;
        out = 0;
        nexts = new ArrayList<>();
        edges = new ArrayList<>();
    }
}

封裝圖中的邊類，屬性包括權重weight，邊的起始節點from，邊的末尾節點to

public class Edge {
    public int weight;
    public Node from;
    public Node to;

    public Edge(int weight, Node from, Node to) {
        this.weight = weight;
        this.from = from;
        this.to = to;
    }
}

封裝圖類，屬性包括所有的節點nodes和所有的邊edges

public class Graph {
    public HashMap<Integer, Node> nodes;
    public HashSet<Edge> edges;
    public Graph() {
        nodes = new HashMap<>();
        edges = new HashSet<>();
    }
}

007寬度優先搜索(BFS，Breadth First Search)是什么？

寬度優先搜索又叫廣度優先。該算法會從指定的第一個頂點開始遍歷圖，先訪問其所有的相鄰點，就像一次訪問圖的一層。換句話說，就是先寬后深的訪問頂點。

008寬度優先遍歷如何實現？

思路：
1. 首先準備一個隊列queue和一個輔助set集合
2. 將指定的第一個頂點入隊queue,并添加到set集合里面
3. 隊列里面的一個頂點出隊并輸出該頂點的值
4. 遍歷該頂點的相鄰頂點，如果set集合里面不包含相鄰頂點cur，則將cur入隊并加入到set集合里面
5. 【3,4】步驟周而復始一次迭代。

//從node出發，進行寬度優先遍歷
public static void bfs(Node node) {
    if (node == null) {
        return;
    }
    Queue<Node> queue = new LinkedList<>();
    HashSet<Node> set = new HashSet<>();
    queue.add(node);
    set.add(node);
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        System.out.println(cur.value);
        for (Node next : cur.nexts) {
            if (!set.contains(next)) {
                set.add(next);
                queue.add(next);
            }
        }
    }
}

009什么叫深度優先搜索(DFS，Depth First Search)？

深度優先搜索算法將會從第一個指定的頂點依次沿著路徑訪問。直到這條路徑最后被訪問了則原路回退并探索下一條路徑。

010深度遍歷的具體實現？

思路：
1. 首先準備一個棧stack和一個輔助set集合
2. 將指定的第一個頂點入棧stack,并添加到set集合里面，然后輸出該頂點的值
3. 棧里面的一個頂點出棧，保存出棧的頂點cur,
4. 遍歷該頂點cur的相鄰頂點nexts，如果set集合里面不包含相鄰頂點cur，則將cur和相鄰節點next都入棧并將next節點加入到set集合里面，輸出相鄰頂點的值，跳出循環。
5. 【3,4】步驟周而復始一次迭代。

public static void dfs(Node node) {
    if (node == null) {
        return;
    }
    Stack<Node> stack = new Stack<>();
    HashSet<Node> set = new HashSet<>();
    stack.add(node);
    set.add(node);
    System.out.println(node.value);
    while (!stack.isEmpty()) {
        Node cur = stack.pop();
        for (Node next : cur.nexts) {
            if (!set.contains(next)) {
                stack.push(cur);
                stack.push(next);
                set.add(next);
                System.out.println(next.value);
                break;
            }
        }
    }
}

011什么是圖的拓撲排序？

舉一個例子，比如打游戲時你一定要先打第一關，因為只有打通了第一關，才能解鎖下一關或下幾關，而不能上來就打第二關。
如下圖1 號端點就相當于第一關，而 6 號端點就相當于是最后一關。所以我們就知道了：
1.找一個入度為零（不需其他關卡通關就能解鎖的）的端點，如果有多個，則從編號小的開始找；
2.將該端點的編號輸出；
3.將該端點刪除，同時將所有由該點出發的有向邊刪除；
4.循環進行 2 和 3 ，直到圖中的圖中所有點的入度都為零；
5.拓撲排序結束；

那么我現在就以上圖為例，詳細分析一下過程；
第一步：輸出 “ 1 ”，并刪除由該點出發的有向邊

第二步：輸出 “ 2 ”，并刪除由該點出發的有向邊

第三步：輸出 “ 3 ”，并刪除由該點出發的有向邊

第四步：輸出 “ 4 ”，并刪除由該點出發的有向邊

第五步：輸出 “ 5 ”，并刪除由該點出發的有向邊

第六步：輸出 “ 6 ”，排序結束。所以，最終拓撲排序的結果是1 2 3 4 5 6

012圖的拓撲排序如何實現？

思路
1. 首先準備一個inMap,其中key為節點node,value為該節點剩余的入度數。然后準備一個隊列zeroInQueue
2. 遍歷圖graph，將圖graph中node和以及節點對應的入度數in存儲到inMap里面,如果該節點的入度數in為0則將該節點入隊zeroInQueue
3. 將隊列zeroInQueue的節點出隊，保存該節點為cur,把cur存儲到集合result里面，遍歷當前節點cur的相鄰節點，將相鄰節點的入度數減1，如果相鄰節點的入度數為0則將該節點入隊zeroInQueue
4. 【3】步驟周而復始一次迭代。

// directed graph and no loop
public static List<Node> sortedTopology(Graph graph) {
    // key：某一個node
    // value：剩余的入度
    HashMap<Node, Integer> inMap = new HashMap<>();
    // 入度為0的點，才能進這個隊列
    Queue<Node> zeroInQueue = new LinkedList<>();
    for (Node node : graph.nodes.values()) {
        inMap.put(node, node.in);
        if (node.in == 0) {
            zeroInQueue.add(node);
        }
    }
    // 拓撲排序的結果，依次加入result
    List<Node> result = new ArrayList<>();
    while (!zeroInQueue.isEmpty()) {
        Node cur = zeroInQueue.poll();
        result.add(cur);
        for (Node next : cur.nexts) {
            inMap.put(next, inMap.get(next) - 1);
            if (inMap.get(next) == 0) {
                zeroInQueue.add(next);
            }
        }
    }
    return result;
}