
- 【用途】這個那個都是圖。很多問題都可以用圖來描述,例如城市的道路規劃。
- 【名詞定義】
- 圖的兩大元素:頂點 (vertex,資料節點) 和 邊 (edge,描述資料節點間的關係)。
- 圖可能是 有向圖 或 無向圖,視其 邊 有無方向性而定。上圖例為有向邊。
- 圖上的邊也可以賦予 權值 (weight),可用來表示兩個頂點間的距離或花費的成本(時間或金錢),或其它限制(如限制卡車最大載重量)。
- 度 (degree):表示跟某個頂點的 鄰接點 數目(鄰居)。在有向圖中,還可以區分成「入邊 in-degree」和「出邊 out-degree」。
- 【實作】紀錄一張圖中頂點之間的關係,有兩種做法:
- 鄰接矩陣 (adjacency matrix):紀錄所有頂點兩兩之間的關係,最直覺簡單,但當頂點數目很多,邊卻很少的情形,會浪費很多記憶體空間。
- 鄰接串列 (adjacency list):只紀錄每個頂點的鄰接點。
- 把圖存入適當的資料結構後,就可以在圖上進行搜尋的動作,常見的做法有兩種:
- 【方便的線上畫圖工具】
- 【範例】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)