【筆記】基礎圖論

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