# 圖論
## dfs
深度優先搜尋法
以下為鄰接矩陣的作法

#include <iostream>
using namespace std;
int vertex,edge;
bool visited[10] = {false};
int maps[10][10] = {{0}};
void dfs(int node);
void print();
int main(){
    cin >> vertex >> edge;
    int tmp1,tmp2;
    for(int i = 0;i < edge;i++){
        cin >> tmp1 >> tmp2;
        maps[tmp1-1][tmp2-1] = maps[tmp2-1][tmp1-1] = 1;
    }
    print();
    cout << endl;
    for(int i = 0;i < vertex;i++){
        if(!visited[i]) dfs(i);
    }
    return 0;
}
void dfs(int node){
    cout << node+1 << " ";
    visited[node] = true;
    for(int i = 0;i < edge;i++){
        if(!visited[i] && maps[node][i] == 1) dfs(i);
    }
}
void print(){
    for(int i = 0;i < vertex;i++){
        for(int j = 0;j < vertex;j++){
            cout << maps[i][j] << " ";
        }
        cout << endl;
    }
}

#include <iostream>
#include <algorithm>
#define N 50
#define M 50
using namespace std;
int graph[N][M];
int visited[N];
void dfs(int n);
int main(){
    fill(visited,visited+N,0);
    int n,m;
    cin >> n >> m;
    int tmp1,tmp2;
    for(int i = 0;i < n;i++){
        cin >> tmp1 >> tmp2;
        graph[tmp1][tmp2] = 1;
        graph[tmp2][tmp1] = 1;
    }
    cout << endl;
    visited[1] = 1;
    dfs(1);
    
    return 0;
}
void dfs(int n){
    cout << n << " ";
    for(int i = 1;i <= 6;i++){
        if(graph[n][i] == 1 && visited[i] == 0){
            visited[i] = 1;
            dfs(i);
        }
    }
}

以上兩種的寫法都是dfs，只是有一些部分不太一樣。
我們程式講解就拿第二個為例子，由於我們是鄰接矩陣，所以建立一個二維陣列來存放資料比較清楚，再建立一個陣列存放node是否被走訪過，那由於此圖是undirected graph(無向圖)，所以假設1連到2，就等於2連到1，接著進入dfs()，我們使用一個迴圈去跑，如果沒被走過且看我們傳入的n有相連的話就將他走訪遞迴，讓走訪過程中走到不能再走後就回傳，雖然我們設的是void，但可以想成回傳一個NULL。
## bfs

#include <iostream>
#include <cstring>
#define vertex 6
#define edge 7
using namespace std;
bool visited[vertex];
int line[edge][2];
void bfs(int n){
    int que[100];
    visited[n] = true;
    int last = -1,first = -1;
    que[++last] = n;
    while(first < last){
        int pop = que[++first];
        cout << pop << " ";
        for(int i = 0;i < vertex;i++){
            if(visited[i] == 0 && line[pop][i] == 1){
                que[++last] = i;
                visited[i] = true;
            }
        }
    }
}
int main(){
    fill(visited,visited+vertex,0);
    memset(line,0,sizeof(line));
    for(int i = 0;i < edge;i++){
        int tmp1,tmp2;
        cin >> tmp1 >> tmp2;
        line[tmp1][tmp2] = line[tmp2][tmp1] = 1;
    }
    for(int i = 0;i < vertex;i++){
        if(!visited[i]){
            bfs(i);
        }
    }


    return 0;
}

首先來看廣度優先搜尋法和深度優先搜尋法的差異:
dfs是用在深度 > 廣度，而bfs是用在廣度 > 深度，所以在做bfs時要注意，我們不是把路走訪到不能走為止，而是走到一個node就要將node同一階層的人都走過，再繼續往下走。
由於dfs和bfs有一些地方相同，所以相似的地方我就不多做贅述了，在bfs()裡我們建立一個佇列(queue)，其實這邊也可以使用STL的queue，但這裡我還是選擇製作一個陣列做撰寫，這邊還有一個地方比較特別的就是我們建立兩個變數分別稱為first和last，代表我們對queue的index，這也是我為甚麼不使用STL的queue，因為對於初學，有index的程式比較好理解，我們先將傳入的n加入佇列裡，接著進入迴圈，這裡的條件是說如果last == first 的時候代表佇列裡已經沒有元素了，所以此時就跳出迴圈，那迴圈的第一個部分是說我們將已經在佇列最前面的元素輸出，也就是pop，剩下的就和dfs類似了。