# 圖的遍歷
## DFS 遍歷法
### 偽碼
```c++
// 偽碼
DFS(u){
vis[u]=true;
for(從 u 出發可到達的所有頂點 v){
if(vis[v]==false) DFS(v);
}
}
DFSTrave(G){
for(G 的所有頂點 u){
if(vis[u]==false) DFS(u);
}
}
```
### 鄰接矩陣
```c++
const int maxv=1000;
const int inf=0x7fffffff;
int n, G[maxv][maxv];
bool vis[maxv]={false};
void DFS(int u, int depth){
vis[u]=true;
for(int v=0;v<n;v++){
if(G[u][v]!=inf && vis[v]==false) DFS(v,depth+1);
}
}
void DFSTrave(int G[][]){
// 訪問 u 所在連通塊
for(int u=0;u<n;u++){
if(vis[u]==false) DFS(u,1);
}
}
```
### 鄰接表
```c++
const int maxv=1000;
vector<int> Adj[maxv];
bool vis[maxv]={false};
void DFS(int u, int depth){
vis[u]=true;
for(int i=0;i<Adj[u].size();i++){]
int v=Adj[u][i];
if(vis[v]==false) DFS(v,depth+1);
}
}
void DFSTrave(vector<int> Adj[]){
for(int u=0;u<n;u++){
if(vis[u]==false) DFS(u,1);
}
}
```
## BFS 遍歷法
### 偽碼
```c++
BFS(u){
queue q;
u 入隊；
inq[u]=true; // 設置 u 已加入隊列
while(q 非空){
取出 q 的隊首元素進行訪問;
for(從 u 出發可到達的所有頂點 v){
if(inq[v]==false){
v 入隊;
inq[v]=true;
}
}
}
}
BFSTrave(G){
for(G 的所有頂點 u){
if(inq[u]==false) BFS(u);
}
}
```
### 鄰接矩陣
```c++
const int maxv=1000;
const int inf=0x7fffffff;
int n,G[maxv][maxv];
bool inq[maxv]={false};
void BFS(int u){
queuq<int> q;
q.push(u);
inq[u]=true;
while(!q.empty()){
u=q.front();
q.pop();
for(int v=0;v<n;v++){
if(inq[v]==false && G[u][v]!=inf){
q.push(v);
inq[v]=true;
}
}
}
}
void BFSTrave(int G[][]){
for(int u=0;u<n;u++){
if(inq[u]==false) BFS(u);
}
}
```
### 鄰接表
```c++
const int maxv=1000;
vector<int> Adj[maxv];
bool inq[maxv]={false};
void BFS(int u){
queue<int> q;
q.push(u);
inq[u]=true;
while(!empty()){
u=q.front();
q.pop();
for(int i=0;i<Adj[u].size();i++){
int v=Adj[u][i];
if(inq[v]==false){
q.push(v);
inq[v]=true;
}
}
}
}
void BFSTrave(vector<int> Adj[]){
for(int u=0;u<n;u++){
if(inq[u]==false) BFS(u);
}
}
```
