---
# System prepended metadata

title: Algorithm
tags: [algorithm]

---

# Algorithm
###### tags: `algorithm`
### ==Breadth-first serach==
>時間複雜度 :　$O(V+E)$
$V為節點 E為邊$

![](https://i.imgur.com/3t8uk2T.png)

#### ==The operation of BFS==
![](https://i.imgur.com/UChhMr4.png)
![](https://i.imgur.com/r11vGLY.png)
![](https://i.imgur.com/6jsJXhS.png)

#### ==Shortest paths==
δ(s,v) : shortest path from s to v
Shortest path參考網站 : 
http://ccisgjt.ddns.net:13001/books/2021110-algorithms/page/algorithms-I8I

#### ==Dijkstra's algorithm== 
> 時間複雜度 : $O(V^2 + E) = O(V^2)$
- 利用**greedy**方法求解


#### ==Bellman-Ford algorithm==
> 時間複雜度 : $O(VE)$ 
- 遍歷方法

### ==Depgth-First Search==
> 時間複雜度 : $O(V+E)$

![](https://i.imgur.com/MUuOGg8.png)

#### The progress of DFS
![](https://i.imgur.com/fT1hgT7.png)
![](https://i.imgur.com/s6coNvi.png)
![](https://i.imgur.com/2ZStwY4.png)
![](https://i.imgur.com/kwpdjVy.png)

#### Topological sort
![](https://i.imgur.com/oKK7kqR.png)
![](https://i.imgur.com/vaf6DdO.png)


### ==Minimum Spanning Tree==

#### ==Kruskal's algorihtm== 
> Complexity : $O(ElogE)$

![](https://i.imgur.com/mXQdOTi.png)
![](https://i.imgur.com/cLFfP2d.png)
![](https://i.imgur.com/hzHNcH0.png)



#### ==Prim's algorithm==
> Complexity : $O(VlogV + ElogV)$, or  $O(E + VlogV)$

![](https://i.imgur.com/QuMR5Nc.png)
![](https://i.imgur.com/h9vtFWH.png)

### ==Single-Source Shortest Paths==
- Single-desination shortest path problem
- Single pair shortest path problem
- All-pair shortest paths problem