# 圖的遍歷&並查集

## 圖的遍歷

定義:從圖上一點出發，走過每個點(僅一次)
應用:在圖上找目標點、檢查兩點是否連通、圖著色、檢查環等等，總之就是暴力搜尋。

### 廣度優先搜尋

Breadth First Search(BFS)，顧名思義，是先走所有相鄰節點的演算法。可以想像成有強迫症的人玩遊戲時會先把所有出現的支線任務解完再前往下一關。

[gif](https://upload.wikimedia.org/wikipedia/commons/4/46/Animated_BFS.gif)

### 實作

因為先遇到的點先處理，所以用先進先出的**queue**
如圖，把目前處理的點(queue最前端的點)連到的所有點都丟入queue中，重複到所有點都走過


[圖源](https://ithelp.ithome.com.tw/articles/10281404)

vector<vector<int>> g; //用鄰接表儲存
vector<int> vis; //紀錄是否走過

void BFS(int start){
    queue<int> q;
    q.push(start); //把起始點加入queue
    vis[start]=1;
    while(!q.empty()){
        int cur=q.front(); //現在要處理的點
        cout<<cur<<"\n";
        q.pop();
        for(int i:g[cur]){ //把所有cur連到的點加入
            if(!vis[i]) q.push(i);
            vis[i]=1;
        }
    }
}

### 應用:最短路

假設我想知道(無權圖上的)節點A最少要走幾部才能到節點B，要怎麼辦?
觀察一下BFS的規律，發現越早走到的節點離起點越近。所以我們只要以A作為起點，把第一次遇到B時的步數傳回即可。

vector<int> dis; //新增一個陣列，儲存各點到A的距離

void BFS(int A,int B){
    queue<int> q;
    q.push(A); 
    vis[A]=1;
    dis[A]=0; 
    while(!q.empty()){
        int cur=q.front();
        if(cur==B) break; //如果先走到B就可以收工了
        q.pop();
        
        for(int i:g[cur]){ 
            if(!vis[i]){
                q.push(i);
                vis[i]=1;
                dis[i]=dis[cur]+1; //如果是由cur走到i，i的距離比cur多1
            } 
        }
    }
}

### 深度優先搜尋

depth First Search(DFS)，與BFS相對，是一直走到沒有路之後才返回走下一條的演算法。可以想像成迷宮走到死路後，返回上一個路口嘗試沒走過的路。

[gif](https://upload.wikimedia.org/wikipedia/commons/7/7f/Depth-First-Search.gif)

### 實作

因為是後發現的點先走，所以使用**遞迴**(較常用，因為簡單)或**stack**

vector<vector<int>> g; //用鄰接表儲存
vector<int> vis; //紀錄是否走過

void DFS(int cur){
    cout<<cur<<"\n";
    vis[cur]=1;
    for(int i:g[cur]){ //檢查cur的所有相鄰點
        if(!vis[i]) DFS(i); //if(沒走過) 那麼就走它
    }
}

### 應用:檢查環

如果在森林中走路時，一直往深處走(DFS)，結果走回原本走過的地方，那麼我們就知道這森林有**環**
有一點需要注意，在有向圖中，A能到B!=B能到A，所以要記錄狀態

假設三種狀態:

| 編號 | 0 | 1 | 2 |
| ---- |:--------:|:----------------------:|:----------------:|
| 意義 | 還沒走過 | 正在走，不確定有沒有環 | 走完了，確定沒環 |

如果我們在走的時候，**碰到編號1的點，那麼此圖有環**

vector<int> type; //紀錄編號

void DFS(int cur){
    type[cur]=1; //正在走，設為1
    for(int i:g[cur]){ 
        if(type[i]==1) cout<<"有環!";
        if(type[i]==0) DFS(i);
    }
    type[cur]=2; //走完了。設為2
}

## 並查集

Disjoint Set Union(DSU)，用來查詢兩個節點是否連通。

### 例題

總共有編號$1-n$號的$n$個人，然後輸入$m$行，每行有兩個數字$a、b$，代表$a$與$b$有血緣關係
現在詢問$q$行，每行有兩個數字$c、d$，問$c$與$d$存不存在血緣關係?

### 題解

如果把每個人視為點，血緣關係視為邊，那麼問題等價於詢問$c、d$是否連通，就可以用並查集處理。

### 概念

並查集的基礎概念是，每個群組選出一個**代表人**，如果兩個點的代表人相同，那麼他們就在同一個群組裡(也就是連通)

首先，不知道血緣關係時，**每個人都是自己的代表**


接下來，假設1號與2號有血緣關係，那麼我們就選擇**一個人作為整個家庭的代表**(選1 or 2都可以)


接著，如果2號與4號也有血緣關係，這時若將2號直接連到4號，會造成2號有兩個代表(1與4)。所以，要合併時，必須是**家族的代表與代表合併**，也就是將1連到4，或4連到1


接著只要照著規則合併所有血緣關係，並查集就完成了。在查詢兩人是否有血緣關係時，只需要查**兩個人的家族代表是否相同**。如果兩人的代表是同一人，那就表示兩人是在同一個家族中，也就是有血緣關係。

(註:如上圖2號，雖然2號的代表會連接到1號，但是必須繼續查詢1號的代表，才能找到**家族的總代表**，也就是4號)

### 名詞導入

觀察上面的圖，我們可以發現一個家族就是一個無還連通圖，也就是**樹**。而對於2號來說，他的代表(1號)稱為2號的**父節點**，反之，2號為1號的**子節點**。而整個家族的總代表(4號)，則稱為整個樹的**根節點**。為了方便描述，以下使用上述名詞介紹。

### 實作

首先，建立陣列p儲存每個節點的父節點，並初始化為自己(n為人數，即陣列大小)

#include <bits/stdc++.h>
using namespace std;

int n=100;
vector<int> p(n+1);

int main()
{
    for(int i=1;i<=n;i++) p[i]=i;
    return 0;
}

接著，撰寫root函式，root(a)即代表a的根節點

int root(int a){
    if(p[a]==a) return a; //若父節點為自身，則為根節點
    return root(p[a]); //否則回傳父節點的根節點
}

合併十分簡單，只要將自己的根節點連到對方的根節點即可

void Merge(int a,int b){
    p[root(a)]=root(b);
}

查詢也十分簡單，只要比較根節點就好

int a,b;
cin>>a>>b;
if(root(a)==root(b)) cout<<"有血緣";
else cout<<"沒血緣";

至此，基礎的並查集已經完成了!

### 優化

我們發現，如果節點距離根節點很遠時，以下圖為例


若要從4找到根節點1，需要耗費大量時間在遞迴root函式上。如果在遞迴的過程中，"順便"將沿路的節點直接連在根節點上，下次再查到時就會快速許多。


修改root函式

int root(int a){
    if(p[a]==a) return a;
     p[a]=root(p[a]);
     return p[a];
}