or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
圖論 I
WiwiHo
https://hackmd.io/@wiwiho/crc1082algo

https://tg.pe/xgaG
基本概念與術語
圖
Graph
❌圖片(picture) ⭕圖(graph)
由一些節點和邊組成的東西
圖的組成
記作 \(G=(V,E)\)
邊
連接兩個節點
無向邊
(undirected edge)
雙向的邊
連接節點 \(u\)、\(v\) 的無向邊
記作 \((u,v)\)、\((v,u)\)
且 \((u,v)=(v,u)\)
i.e. 記作無序對
有向邊
(directed edge)
單向的邊
從 \(u\) 到 \(v\) 的有向邊
記作 \((u,v)\)
i.e. 記作有序對
權重
邊或點上可能有權重
有就稱為帶權
圖上的東西
Note:
畫圖講
特殊圖
Note:
畫圖講
樹
沒有環的連通圖
性質
有根樹
無根樹上的任何一個節點都可以當作根
變成有根樹
有根樹上會出現東西
Note:
畫圖講
儲存
鄰接矩陣
一個 \(|V| \times |V|\) 的矩陣
記作 \(M\)
\(M_{u,v}\) 是邊 \((u,v)\) 的資訊
e.g. 存不存在、權重
空間複雜度:\(O(|V|^2)\)
時間複雜度:
\(M=\begin{bmatrix} \text{X} & 10 & \text{X} & 2 & 5 \\ 10 & \text{X} & 7 & 3 & \text{X} \\ \text{X} & 7 & \text{X} & \text{X} & \text{X} \\ 2 & 3 & \text{X} & \text{X} & \text{X} \\ 5 & \text{X} & \text{X} & \text{X} & \text{X} \end{bmatrix}\)
Note:
注意無向圖和重邊
鄰接串列
開 \(|V|\) 個大小可變的容器
第 \(i\) 個存節點 \(i\) 的鄰邊或出邊資訊
空間複雜度:\(O(|V|+|E|)\)
時間複雜度:
鄰接矩陣和鄰接串列的比較
空間複雜度
鄰接矩陣:\(O(|V|^2)\)
鄰接串列:\(O(|V|+|E|)\)
時間複雜度
樹的儲存
遍歷
深度優先搜尋
Depth-First Search
盡量往深處走
Note:
畫圖講過程
某種遞迴
呼叫 \(dfs(v)\) \(\Rightarrow\) \(v\) 入堆
\(\Rightarrow\) \(v\) 入點
\(dfs(v)\) 結束 \(\Rightarrow\) \(v\) 出堆
\(\Rightarrow\) \(v\) 出點
入點順序:前序
出點順序:後序
時間複雜度:\(O(|V|+|E|)\)
廣度優先搜尋
Breadth-First Search
先把所有知道可以走的點走完
Note:
畫圖講過程
Note:
注意 vst
BFS 的順序
由起點開始擴散
https://www.youtube.com/watch?v=x-VTfcmrLEQ
離起點進的先、離起點遠的後
\(\Rightarrow\) 可以拿來做不帶權圖最短路徑
Note:
畫圖講
時間複雜度:\(O(|V|+|E|)\)
一些圖上的經典問題
更經典的下一堂課才會講 (?
表格上的問題
\(N \times M\) 的二維表格可以視為
有 \(N+M\) 個節點的圖
如果某兩個格子可以互通
那就在它們兩個的節點之間連邊
小技巧:
通常能互通的格子相對位置是固定的
所以直接去看相對位置就好
Note:
這題最短路徑長是含起終點的格子數
不帶權最短路徑
\(\Rightarrow\) BFS
歐拉路徑
Euler path
一條經過所有的邊
且不經過重複的邊
但可以經過重複的點的路徑
有歐拉路徑的條件
無向圖:
恰有 0 個或 2 個度數是奇數的點
有向圖:
所有點的入度等於出度
或有恰一個點的入度比出度多 1
和恰一個點的出度比入度多 1
求歐拉路徑
對邊 DFS
再把出點順序倒過來
漢米爾頓路徑
Hamiltonian path
經過所有點恰一次的路徑
(起終點相同不算重複)
位元 DP
Note:
看講義
講旅行推銷員
藏在問題裡的圖
有時候題目裡不會出現任何關於圖的關鍵字
看起來也沒有類似點、邊的東西
但解法卻和圖論有關
Note:
口頭講作法
Note:
口頭講作法
一些樹的經典問題
樹直徑
在樹上最長的簡單路徑
作法
先隨便找一個點 \(u\)
找到離它最遠的點 \(v\)
再找到離 \(v\) 最遠的點 \(w\)
\(v\) 到 \(w\) 的簡單路徑就是樹直徑
兩次 DFS
樹圓心
以它為根時
樹的深度會最小的點
Note:
會在直徑上
樹重心
把一個節點 \(v\) 從樹上拔掉
出現的連通塊大小都不超過本來點數的一半
\(v\) 就是樹重心
性質
Note:
看講義,口頭講
二元樹
每個節點最多只有兩個子節點的有根樹
有時候子節點會有左右之分
Note:
講左右子節點、子樹、兄弟節點
性質
Note:
講證明
特殊的二元樹
Note:
看講義講
二元樹的儲存
二元樹的遍歷
Note:
中序性質口頭講