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
---
DSA 第十一週講義
tags:
DSA
Data Structure and Algorithm
資料結構
演算法
Data Structure
Algorithm
tcirc39th
社課
臺中一中電研社
社網:tcirc.tw
online judge:judge.tcirc.tw
IG:TCIRC_39th
社課點名表單:google 表單
圖論(graph)
介紹
圖(graph),是一種用來表示關聯、關係的概念,由數個點(vertex)與數個邊(edge)組成,邊可以用來連接任兩點,表示兩點之間有關係
點
個別的資料點,若沒有邊,每個點都是獨立的(與其他點沒有關係)
ex.車站、人
邊
用來連通兩個點,表示點與點的關係,分成有向邊和無向邊
有向邊:代表兩個點之間具有單向關係,只有一個方向有通(可以從A點走到B點,但不能從B點走到A點)
無向邊:代表兩個點之間具有雙向關係,雙向互通
ex.鐵路、朋友關係
權重
有些情況下,點與點的關係與數值有關,這時可以幫邊加上權重
圖的儲存
沒有學會如何儲存圖,就沒辦法做圖的題目,所以先來看看圖的儲存方式吧
圖的實用儲存方式有以下2種
Adjacency matrix
Adjacency list
Adjacency matrix
中文叫「相鄰矩陣」,當點的數量為N,用一個N*N的二維陣列儲存,適合用於邊比點多很多的情況
可以看到,當點多而邊少(相對),Adjacency matrix浪費了不少空間
但是當邊的數量接近或超過N*N,或是重複的邊常常出現的話,Adjacency matrix可以將重復的那一格加1,就能節省不少空間
Adjacency list
中文叫「相鄰列表」,當點的數量為N,儲存方式為,宣告一個長度為N的一維陣列,陣列資料型態使用vector或list ,適合用於點多,而邊不多的情況
可以看到,當點多而邊少(相對),Adjacency list節省了不少空間
但是當邊的數量接近或超過N*N,或是重複的邊常常出現的話,Adjacency list就會浪費不少空間
樹 vs 圖
樹的定義較為嚴格,樹的每個點須與其他點連通,且不能形成環,圖則無此規定
最小生成樹
全名為最小權重生成樹,也就是把一個無向圖中取出一顆樹,且樹包含所有點。
下面將簡單介紹如何求出最小生成樹。
Kruskal_Algorithm
將每個點視作獨立的樹。接著,將權重由小到大,將兩個不同的樹連在一起。若選到的邊會讓樹形成一個環,就跳過不執行合併。
來源
這裡有個新的概念,叫DSU演算法,又稱併查集。可用於分類的問題。由兩個功能組成,查詢和合併。
套用到圖論,我們可以將起始的每個節點視為獨立的樹,而我們的目標就是將這些樹結合為最小生成樹。
在DSU裡,我們會開一個陣列root紀錄每個節點屬於哪顆樹,若兩個節點在同個樹裡,則它們的根節點相同,所以會有同一個root。
查詢的部分,就是查詢每個節點的root。
至於將兩棵樹合併成同一棵樹時,只需要將兩棵樹的root變成同一個就好。但是要先檢查它們的root是否不同,否則最後會求出一個環。
https://ideone.com/LBgxEo
輸出太長,這裡就先不放
Prim_Algorithm
選擇任一樹根作為樹根(起點)。接著,尋找尚未加入樹的點中,離樹根最近的點加入樹。重複此步驟直到所有點加進樹裡。

來源
output
https://ideone.com/dQel5R
圖的遍歷
圖的便利方式有兩種
BFS:廣度優先搜尋
DFS:深度優先搜尋
BFS
又稱廣度優先搜尋,是一種遍歷整個圖的演算法。一開始先選擇一個點最為起始點,並往周圍連結的點散開。持續上述步驟直到所有的點都被讀取過。

連結
圖論和樹的廣度優先搜尋一樣,我們可以拿queue實作。先挑選一個點,把他加進queue裡,接著讀取queue第一個元素,將和它連結的點加進queue。
所以整個流程就是:
讀取 –>pop –>加進周圍的點 –>讀取
直到沒有元素在queue裡時,我們可以停止了,因為已經拜訪過每個和出發點有連通的點了。
要注意的是,不要將已被拜訪過的元素加進queue裡,否則程式不會停止(因為會永遠讀不完)。所以可以開個陣列紀錄是否已走訪過該元素。
為了實際了解bfs的應用,我們參考下面的例題。
套用到圖論也是相同概念

來源
例題: 倒水時間
這題是非常典型的bfs應用,雖然不明顯看出他是一個圖。不過可以把每個水管看成是一個點,所以此圖變成一個有向圖(方向由上而下,往右或往左),兩相鄰的點形成一邊。
0 0 1 0 0

0 0 1 1 0
0 1 1 1 1
1 1 0 0 0
由於題目已經指定由上面倒水,所以我們將第一排的點都設為1。接著將第一排的水管都加進queue裡。
後面就簡單了,重複執行上述我們所說的步驟。
至於往上的水管,就只是要多拜訪一個元素。
DFS
又稱深度優先搜尋

圖源
造訪順序
1.由root當起點,選擇一個child拜訪,再由這個node(節點)繼續選擇一個child拜訪,不斷重複直到遇到leaf(沒有子節點)
2.從現在這一層sbiling(同層的其他節點)中選一個當起點,執行步驟1,不斷重複直到該層的sbiling都已經拜訪過
3.處理往上一層的其他sbiling,執行步驟2,不斷重複直到回到root那一層
可以發現我們在過程中都是先處理剛加入的節點,所以適合用stack–先進先出的概念來實做
作法:
例題: 觀光景點
有n個點,n-1個邊,任兩點間一定會有單一路徑連通(代表這是一棵樹),請求出與起點相關性大於等於q的景點數量(不包含起點本身)
兩景點間的相關性為沿路的邊中,權重最小的,所以如果在行經的路線中遇到權重小於題目要求的,就不用再走下去了(因為之後遇到的景點關連性都會小於q)
換句話說,當邊的權重<q,那條邊就可以直接不要連了,反正通過那條路後的所有景點都不符合題目要求,所以我們不須額外紀錄邊的權重,只需要遍歷與起點連通的所有點,並記錄這些點的數量就可以了。
注意!:需要另外開一個一維陣列紀錄每個點有沒有被走訪過,有被走訪過的點不能再走(不然你的遍歷永遠不會結束)
我們這次試試看用dfs的方式遍歷吧(要用 bfs 或是 dsu 也可以)
邊和點差不多,且不用紀錄權重,可以用adjacency list,不過點的數量不算太多,要用adjacency matrix也行