如果和其他演算法相關的系列文比較，就會發現差不多也涵蓋完了基本的資料結構，在以資料結構來討論裡面，圖通常是大家的最後一站(撇除部分系列文會討論更高階的資料結構)。

資料結構

圖的資料結構其實可以說是樹結構的進階版。
我們前面主要探討的是二元樹，圖就像多元樹(子樹數量可能 >= 2)，但可能有環的版本。
圖的程式碼寫法並無固定，以 [Wiki](https://zh.wikipedia.org/zh-tw/%E5%9B%BE_(%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84)) 中的定義來看，圖的關鍵元素就是節點和邊。
聽起來是不是和樹很像？所以我才會說圖的結構有些概念和樹是相通的，特別是簡單的圖，很容易看到樹的影子。

權重與方向性

圖的重要元素是節點和邊，相較一般樹的題目，在圖相關的題目裡，有些邊會有權重和方向性，這是樹的結構裡相對少被提到的。
權重：兩個節點相連的邊，A 節點到 B 節點的成本，通常無特別單位，權重也有分正負，如果是單純只有正權重題目會比較簡單，還有負的在邊界的過濾和路徑的選擇上就要注意更多。以二元樹來說，我們如果把所有節點到相鄰邊的成本都算為等重，則稱作「無權」，相對的，剛剛介紹有權重就會稱作「有權」。
方向性：圖裡的節點題目有可能會說點與點間的路徑，是雙向還是單向的，雙向的稱為「無向」，因為只要有路徑，兩個點可以任意來回，單向的稱為「有向」，只能以題目給予的方向行進。會影響路徑的選擇。

環

有環無環是和權重與方向性一樣，也是圖論相關題目會特別提到的特性。
上一個我們提到有環無環的地方是鏈結串列的單元，其實概念是相近的。
有環指的是隨著題目給予的路徑做遍歷，最後不會走到一個終點，而可以無限循環下去，這稱作有環。
如果隨著路徑做遍歷，最後會停在某個點上，則稱作無環。

All Paths From Source to Target

讓我們今天在看完圖的基本性質後，我們先用一題簡單的題目來了解一下圖論題目的樣貌。
畢竟是講圖的單元，讓我把圖帶過來。

說了圖論中重視路徑(連接節點的邊)概念，通常題目會用兩種方式來指示圖的路徑，一種是陣列、一種是矩陣。通常稱為相鄰陣列和相鄰矩陣，兩種表示方式可以相互轉換。
以這題來說，題目的範例 1 用這樣的方式表示圖：

graph = [[1,2],[3],[3],[]]

指的是陣列的 index 代表節點本身的值(編號/ID)，graph[i] 指的是點 i 有路徑相連、可以從點 i 到的點。
例如 graph[0] = [1,2] 的意思就是點 0 有兩個路徑，一個連到點 1，一個連到點 2。
而 graph[3] = [] 表示這個點是其中一個終點，沒有從這個點出發的路徑。

這題明確寫明了這是一個 directed acyclic graph(DAG)，翻成中文就是 有向 無環 圖，是圖論相關題目中結構單純的題目，因為有向和無環，我們只管隨著給予的路徑走，便能夠遍歷整張圖，也不會有無窮迴圈的狀況。
題目給予了一張圖，要求我們回傳所有從第一個節點走到最後一個節點的路徑。

遍歷圖的方式一般有兩種，深度優先和廣度優先，在前面樹的單元有提過，圖的單元我會用一篇來討論深度優先和廣度優先在遍歷圖的優缺點和題目比較。

因為題目要求的是「路徑」，我們在做函式的時候務必有一個變數是來存走過的點的，我稱呼他為 path。
會另外宣告一個函式來做遞迴，終止條件是當目前的點是目標點的時候，紀錄走過的路線。
一進入函式，我們先把現在走到的點加入 path(表示經過了這個點)，然後做終止判斷，確認是否到終點了。
如果還沒到終點，那我們就要看目前走到的點，對應題目給的路徑，還有哪些路徑可以走，然後每條路徑都嘗試走走看。
最後發現這點已經沒有路徑可以走了，表示我們不應該走這點，我們再把路徑中保存的這點移除，回退到上一個點，看看其他路徑怎麼走。

上面是這題的邏輯，接著讓我們看看這題的程式碼。

public class Solution {
    public List<IList<int>> Result;
    public IList<IList<int>> AllPathsSourceTarget(int[][] graph) {
        Result = new List<IList<int>>();
        Traverse(graph, 0, graph.Length - 1, new List<int>());
        return Result;
    }
    public void Traverse(int[][] graph, int currentNode, int target, List<int> path){
        path.Add(currentNode);
        if(currentNode == target){
            Result.Add(new List<int>(path));
            path.Remove(currentNode);
            return;
        }
        for(var i = 0; i < graph[currentNode].Length; i++){
            Traverse(graph, graph[currentNode][i], target, path);
        }
        path.Remove(currentNode);
    }
}

因為這題給的圖是無環有向，所以可以很容易的遍歷，題目本身看起來也還有些樹的影子在。
明天我們再來看進階一些的題目，更深入了解怎麼處理圖的題目。