【筆記】基礎圖論

• 【用途】這個那個都是圖。很多問題都可以用圖來描述，例如城市的道路規劃。
• 【名詞定義】
  • 圖的兩大元素：頂點 (vertex，資料節點) 和 邊 (edge，描述資料節點間的關係)。
  • 圖可能是 有向圖 或 無向圖，視其 邊 有無方向性而定。上圖例為有向邊。
  • 圖上的邊也可以賦予 權值 (weight)，可用來表示兩個頂點間的距離或花費的成本(時間或金錢)，或其它限制(如限制卡車最大載重量)。
  • 度 (degree)：表示跟某個頂點的 鄰接點 數目(鄰居)。在有向圖中，還可以區分成「入邊 in-degree」和「出邊 out-degree」。
• 【實作】紀錄一張圖中頂點之間的關係，有兩種做法：
  • 鄰接矩陣 (adjacency matrix)：紀錄所有頂點兩兩之間的關係，最直覺簡單，但當頂點數目很多，邊卻很少的情形，會浪費很多記憶體空間。
  • 鄰接串列 (adjacency list)：只紀錄每個頂點的鄰接點。
• 把圖存入適當的資料結構後，就可以在圖上進行搜尋的動作，常見的做法有兩種：
  • BFS (Breadth First Search，廣度優先搜尋)【筆記】
  • DFS (Depth First Search，深度優先搜索)【筆記】
• 【方便的線上畫圖工具】
  • Graph online
  • Draw Graph
• 【範例】ZeroJudge a290: 新手訓練系列 ~ 圖論 【題解】
  • 輸入有兩個正整數 N, M ( N <= 800, M <= 10000 )，代表有 N 個城市 M 條道路。道路是有方向性的!
  • 接下來有 M 行， 每行有 2 個正整數 a, b ( 1 <= a, b <= N )，代表 a城市可以到 b城市。

int N, M, a, b;
vector <int> g[n];

cin >> N >> M;
for (int i=0; i<M; i++){
	cin >> a >> b;
	g[a].push_back(b);
}

Python code (credit: Amy Chou)
【做法1】用 list 存圖
【做法2】用 dictionary 存圖

# N vertex (1 ~ N), M edges

G = [list() for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    G[a].append(b)

# N vertex (1 ~ N), M edges

graph = {k: [] for k in range(N+1)}
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)