Q1. Graph 是什麼

• Graph 定義：一個 graph 由 數個點( vertex )與數個邊( edge ) 組成
• 圖形的表示有兩種方法：相鄰矩陣 (Adjacency Matrix) 、相鄰串列 (Adjacency List)

  • 相鄰矩陣 (Adjacency Matrix) 使用二維陣列實作的優點：

    • 適合儲存 edge 很多的圖形，若 vertex 很多但是 edge 很少，容易造成稀疏矩陣，浪費記憶體空間
    • 適合需要經常判斷 edge 是否存在的問題
      

  • 相鄰串列 (Adjacency List) 使用 Linked list 實作的優點：

    • 適合儲存 vertex 很多，但是 edge 很少的圖形
    • 能夠彈性使用記憶體

    # 與 1 相鄰的點有 2, 5
    Adj[1] = [2, 5]
    # 與 2 相鄰的點有 1, 3, 4, 5
    Adj[2] = [1, 3, 4, 5]
    Adj[3] = [2, 4]
    Adj[4] = [2, 3, 5]
    Adj[5] = [1, 2, 4]
    

    

圖片來源：https://kopu.chat/2017/09/22/實作graph與dfs、bfs走訪/

Q2. 學會 Graph 概念可以做什麼 ?

• 生活中的 Graph 問題
  • 例如 路線規劃問題
• 圖論著名題目，一筆畫問題

參考資料：https://zh.wikipedia.org/wiki/图论

Lab. 明天要解的題目：997. Find the Town Judge

• 題目連結：https://leetcode.com/problems/find-the-town-judge/

• 題目敘述：

  • 一個小鎮中有編號 1 ~ n 的人，謠傳這些人之中，有一個人是秘密的小鎮法官。
  • 如果真的有法官，則法官會滿足這幾個條件：
    • 這位法官不會相信任何人。
    • 法官以外的所有人，都相信法官。
    • 整個小鎮只會恰有一個人滿足這些條件。
  • 給定鎮民之間的信任關係，要找出法官是誰。
    

• 測資的 Input/Output

  • input 為 小鎮上有 n 個人 與 紀錄了信任關係的二維陣列 trust
  • output 需要回傳誰是小鎮的法官，若無則回傳 -1
    

• 題目的條件

  • 小鎮上的人有 1~1000人

  • 小鎮上的 trust 長度為 1~10000 間

  • trust 的 column 數量為 2
    

  • trust 中的紀錄不會重複

  • 鎮民不會信任自己

  • trust 中的鎮民一定在 1 ~ n 之間