上一篇：
[← STL筆記](https://hackmd.io/Az-1YypcS3iFLrHWwZg-bw)
:::warning
要有一定STL基礎
:::

DFS
---
+ 深度優先搜尋 Deep First Search
+ 盡可能往較深的節點走
+ 可以用來計算樹的**深度**或**最長路徑**
+ 實作程式碼：

BFS
---
+ 廣度優先搜尋 Breadth First Search
+ 盡可能往較淺的節點走
+ 適合計算**最短路徑**
實作程式碼：[zj a290.新手訓練系列 ~ 圖論](https://zerojudge.tw/ShowProblem?problemid=a290)

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
	
    int n, m, a, b, A, B;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //cin & cout 優化 不加不能AC哦QAQ
    //這個建議背起來
    
    while (cin >> n >> m)
    {
    	vector<int> edge[801];
    	for (int i = 0; i < m; i++)
    	{
    	    cin >> a >> b;
    	    edge[a].push_back(b);  //把a連接到b
    	}
    	cin >> A >> B;
    	queue<int> q;      //先進先出FIFO
    	q.push(A);         //A是起點
    	bool ans = false;  //設ans判斷是否能走到
    	while (!q.empty()) 
    	{
    	    int i = q.front();
    	    q.pop();       //移除已走訪的節點
    	    if (i == B)
            {
                ans = true;				
                break;
            }
            for (int j: edge[i])
            	q.push(j); //將所有i連接到的點塞進queue
        }
        if (ans) cout << "Yes!!!\n";
        else cout << "No!!!\n";
    }
    return 0;
}

Dijkstra
---
+ 具有權重的BFS
+ 計算最短路

程式碼：

struct node
{
    int to, w;
};
vector<node> edge[N];
vector<int> d(N, 0x3f3f3f3f);

priority_queue<pair<int, int>> pq;
pq.push({0, 起始點編號});
d[起始點編號] = 0;

//只要pq不是空的就繼續走訪
while (!q.empty())
{
    //取出(負路徑長w, 編號點u)，並檢查-w是否與當前總長相同
    tie(w, u) = pq.top(); pq.pop();
    if (-w != d[u]) continue;
    
    //對d[新的點] > d[目前點] + w 的情況更新總長
    for (auto i: edge[[u]])
        if (d[i.to] > d[u] + w)
        {
            d[i.to] = d[u] + i.w;
            pq.push({-d[i.to], i.to});
        }
}

___
上一篇：
[← STL筆記](https://hackmd.io/Az-1YypcS3iFLrHWwZg-bw)