001圖相關(guān)的術(shù)語有哪些？

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

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

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

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

003鄰接矩陣的問題？

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

004什么是圖的鄰接表？

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

005圖的鄰接表問題？

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

006如何來封裝一個圖？

封裝圖中的節(jié)點類，屬性包括節(jié)點對應(yīng)的值value，收斂進(jìn)來的節(jié)點個數(shù)in，發(fā)散出去的節(jié)點個數(shù)out,從該節(jié)點發(fā)散出去并直接相連的節(jié)點nexts，該節(jié)點包含的邊數(shù)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<>();
    }
}

封裝圖中的邊類，屬性包括權(quán)重weight，邊的起始節(jié)點from，邊的末尾節(jié)點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;
    }
}

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

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

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

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

008寬度優(yōu)先遍歷如何實現(xiàn)？

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

//從node出發(fā)，進(jìn)行寬度優(yōu)先遍歷
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什么叫深度優(yōu)先搜索(DFS，Depth First Search)？

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

010深度遍歷的具體實現(xiàn)？

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

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什么是圖的拓?fù)渑判颍?/h2>

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

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

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

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

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

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

第六步：輸出 “ 6 ”，排序結(jié)束。所以，最終拓?fù)渑判虻慕Y(jié)果是1 2 3 4 5 6

012圖的拓?fù)渑判蛉绾螌崿F(xiàn)？

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

// directed graph and no loop
public static List<Node> sortedTopology(Graph graph) {
    // key：某一個node
    // value：剩余的入度
    HashMap<Node, Integer> inMap = new HashMap<>();
    // 入度為0的點，才能進(jìn)這個隊列
    Queue<Node> zeroInQueue = new LinkedList<>();
    for (Node node : graph.nodes.values()) {
        inMap.put(node, node.in);
        if (node.in == 0) {
            zeroInQueue.add(node);
        }
    }
    // 拓?fù)渑判虻慕Y(jié)果，依次加入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;
}