2022/06/14

簡單輕鬆十分鐘學會 Graph (圖) 刷 LeetCode

一、Graph

1.1 基本觀念介紹


此處談及的 Graph 並不是指圖片或者圖形，而是由數個 vertex (點) 及數條 edgs (邊) 所構成；點與點之間以邊相連，表示這兩點有關聯性。


而一個頂點的 degree (度) 指與該頂點相連的邊的條數。


兩點之間也可以有很多條邊，代表這兩點有很多項關聯；一個點有連到自己的邊，稱之為self-loop (自環)，表示自己和自己有關聯。



1.1.1 Isomorphism / Isomorphic




(https://web.ntnu.edu.tw/~algo/Graph.html)


如果兩張圖的連接方式一模一樣時，則稱作同構圖。圖上的點可以任意移動位置，不論點的位置如何，都不會改變點與點之間的關聯。




1.1.2 Directed & Undirected graph



(https://web.ntnu.edu.tw/~algo/Graph.html)


邊也可以擁有方向性，用來表示兩點間的關係是單向或雙向的。


  • 有向圖，邊有方向性，表示兩點之間為單向關係。

  • 無向圖，邊無方向性，表示兩點之間為雙向關係。




1.1.3 Weighted graph 權重



(https://web.ntnu.edu.tw/~algo/Graph.html)



圖上的點和邊都可以擁有權重，可做其他用途，如航空路線圖、GPS 導航等。




1.1.4 名稱或代號


 


(https://web.ntnu.edu.tw/~algo/Graph.html)


點和邊上面可以取名字、代號利於辨認，可以寫在點和邊的旁邊，也可以寫在點的裡面、邊的上面，只要能表達清楚就好，通常是用英文字母及數字居多。





1.2 圖的資料結構


1.2.1 Adjacency Matrix


(https://web.ntnu.edu.tw/~algo/Graph.html)


把一張圖上的點依序標示編號，然後建立一個方陣記錄連接的資訊；連接資訊可以是邊的數目，也可以是邊的權重，也可以儲存其他的資訊。




1.2.2 Adjacency Lists


(https://web.ntnu.edu.tw/~algo/Graph.html)


把一張圖上的點依序標示編號。每一個點，後方列出所有相鄰的點。




1.3 Graph Traversal


通常圖的題目都會之前介紹過的 DFS 和 BFS 搭配前面介紹過圖的資料結構去解，圖的資料結構還有很多種，這邊只是舉出常用的，端看題型搭配哪種比較好解

  • Depth-first Search (深度優先搜尋)
  • Breadth-first Search (廣度優先搜尋)



1.4 實際運用範例


  • 建設規劃 : 電子電路、航空控制、行車導航、電信設施、物流線路

  • 社交網路： Facebook 利用圖來推薦你可能認識的朋友

  • 推薦系統： Amazon / Netflix 利用圖來推薦產品與電影





二、題目整理


Graph 常出現之 LeetCode 題目整理



關於這個 excel 表，你可以 :
  • 題號 : 根據 LeetCode 題目出現的頻率, top interview 150 等整理的，但注意不代表這就涵蓋所有面試會考的題目。或你可以選擇 Grind 來安排你要刷的題目
  • 難度 : 按照你現在想要的難度選擇刷題
  • 重要性 : 比如說你注意到、或別人提到 Google 很常考這個題目之類，可以設定你覺得相對的重要性，之後可以拿來篩選用
  • 第一次是否解出來 : 紀錄解題是否第一次就成功，若不成功可能需要複習
  • 解題思路 : 題目的思路過程，寫大綱就好不用寫很詳細
  • 其他解法 : 若解出來是否還可以想到其他解法，或是看到別人提供了更好的解法便記錄下來，在面試時還可以提出自己有不同解法
  • 學到技巧 : 如此題可以用 two pointer 來解，寫下來下次遇到別的題目就可以知道說我多一個解法可以想想看可不可行
  • 複習次數 : 用來記錄第一次解不出來的題目之練習次數
  • 複習筆記 : 有可能再做一次還是解不出來，那可寫下這次癥結點是什麼，怎麼解決的，盡量完全理解解法，讓自己如果再做一次題目時若還是卡住，可以看筆記或是回想筆記試圖解出來
  • 上次解題時間 : 可用來篩選下次該複習的題目







三、References





By -
Tags , , , , , , ,

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)