算法：深度優先算法和廣度優先算法

算法：深度優先算法和廣度優先算法(基於鄰接矩陣)

1.寫在前面

　　圖的存儲結構有兩種：一種是基於二維數組的鄰接矩陣表示法。

　　　　　　　　　　　　另一種是基於鏈表的的鄰接表。

　　在鄰接矩陣中，可以如下表示頂點和邊連接關系：

說明：

　　將頂點對應為下標，根據橫縱坐標將矩陣中的某一位置值設為1，表示兩個頂點向聯接。

　　圖示表示的是無向圖的鄰接矩陣，從中我們可以發現它們的分布關於斜對角線對稱。

　　我們在下面將要討論的是下圖的兩種遍歷方法（基於矩陣的）：

　　我們已經說明了我們要用到的是鄰接矩陣表示法，那麼我首先要來構造圖：

　　矩陣圖的數據結構如下表示：

#define MaxVnum 50
typedef double AdjMatrix[MaxVnum][MaxVnum];   //表示一個矩陣，用來存儲頂點和邊連接關系
typedef struct {
    int vexnum,arcnum;　　　　　　　　　　　　　　 //頂點的個數，邊的個數
    AdjMatrix arcs;　　　　　　　　　　　　　　　　 //圖的鄰接矩陣
}Graph;

　　這樣我們可以首先來創建上述圖，為了方便，我們直接在代碼中書寫矩陣，而不用每次調試手動輸入了

void CreateGraph(Graph &G)
{
    G.vexnum=8;
    G.arcnum=9;
    G.arcs[0][1]=1;
    G.arcs[0][2]=1;
    G.arcs[1][3]=1;
    G.arcs[1][4]=1;
    G.arcs[2][5]=1;
    G.arcs[2][6]=1;
    G.arcs[3][1]=1;
    G.arcs[3][7]=1;
    G.arcs[3][6]=1;
    G.arcs[4][1]=1;
    G.arcs[4][7]=1;
    G.arcs[5][2]=1;
    G.arcs[5][6]=1;
    G.arcs[5][5]=1;
    G.arcs[6][2]=1;
    G.arcs[6][5]=1;
    G.arcs[7][3]=1;
    G.arcs[7][4]=1;
}

　　這樣我們就已經完成了准備工作，我們可以正式來學習我們的兩種遍歷方式了。

2.深度優先遍歷算法

　　分析深度優先遍歷

　　　　從圖的某個頂點出發，訪問圖中的所有頂點，且使每個頂點僅被訪問一次。這一過程叫做圖的遍歷。

　　　　深度優先搜索的思想：

　　　　　　①訪問頂點v；
　　　　　　②依次從v的未被訪問的鄰接點出發，對圖進行深度優先遍歷；直至圖中和v有路徑相通的頂點都被訪問；
　　　　　　③若此時圖中尚有頂點未被訪問，則從一個未被訪問的頂點出發，重新進行深度優先遍歷，直到圖中所有頂點均被訪問過為止。

　　　　比如：

　　　　在這裡為了區分已經訪問過的節點和沒有訪問過的節點，我們引入一個一維數組bool visited[MaxVnum]用來表示與下標對應的頂點是否被訪問過，

流程：
☐ 首先輸出 V1，標記V1的flag=true;
☐ 獲得V1的鄰接邊 [V2 V3],取出V2，標記V2的flag=true;
☐ 獲得V2的鄰接邊[V1 V4 V5],過濾掉已經flag的，取出V4，標記V4的flag=true;
☐ 獲得V4的鄰接邊[V2 V8],過濾掉已經flag的，取出V8，標記V8的flag=true;
☐ 獲得V8的鄰接邊[V4 V5],過濾掉已經flag的，取出V5，標記V5的flag=true;
☐ 此時發現V5的所有鄰接邊都已經被flag了，所以需要回溯。（左邊黑色虛線，回溯到V1，回溯就是下層遞歸結束往回返）
☐
☐ 回溯到V1，在前面取出的是V2，現在取出V3，標記V3的flag=true;
☐ 獲得V3的鄰接邊[V1 V6 V7]，過濾掉已經flag的,取出V6，標記V6的flag=true;
☐ 獲得V6的鄰接邊[V3 V7],過濾掉已經flag的,取出V7，標記V7的flag=true;
☐ 此時發現V7的所有鄰接邊都已經被flag了，所以需要回溯。（右邊黑色虛線，回溯到V1，回溯就是下層遞歸結束往回返）

　　深度優先搜索的代碼

bool visited[MaxVnum];
void DFS(Graph G,int v)
{
    visited[v]= true; //從V開始訪問，flag它
    printf("%d",v);    //打印出V
    for(int j=0;j<G.vexnum;j++) 
        if(G.arcs[v][j]==1&&visited[j]== false) //這裡可以獲得V未訪問過的鄰接點
            DFS(G,j); //遞歸調用，如果所有節點都被訪問過，就回溯，而不再調用這裡的DFS
}

void DFSTraverse(Graph G) {
    for (int v = 0; v < G.vexnum; v++)
        visited[v] = false; //剛開始都沒有被訪問過

    for (int v = 0; v < G.vexnum; ++v)
        if (visited[v] == false) //從沒有訪問過的第一個元素來遍歷圖
            DFS(G, v);
}

 3.廣度優先搜索算法

　　　　分析廣度優先遍歷　　　　

　　　　　　所謂廣度，就是一層一層的，向下遍歷，層層堵截，還是這幅圖，我們如果要是廣度優先遍歷的話，我們的結果是V1 V2 V3 V4 V5 V6 V7 V8。

　　　　　　廣度優先搜索的思想：

　　　　　　 　　① 訪問頂點vi ；

　　　　　　　　 ② 訪問vi 的所有未被訪問的鄰接點w1 ,w2 , …wk ；

　　　　　　　　 ③ 依次從這些鄰接點（在步驟②中訪問的頂點）出發，訪問它們的所有未被訪問的鄰接點; 依此類推，直到圖中所有訪問過的頂點的鄰接點都被訪問；

　　　說明：

　　　　　　為實現③，需要保存在步驟②中訪問的頂點，而且訪問這些頂點的鄰接點的順序為：先保存的頂點，其鄰接點先被訪問。 這裡我們就想到了用標准模板庫中的queue隊列來實現這種先進現出的服務。

　　　　　　老規矩我們還是走一邊流程：

　　　說明：　

　　　　 ☐將V1加入隊列，取出V1，並標記為true(即已經訪問)，將其鄰接點加進入隊列，則 <—[V2 V3]　

　　　　 ☐取出V2，並標記為true(即已經訪問)，將其未訪問過的鄰接點加進入隊列，則 <—[V3 V4 V5]

☐取出V3，並標記為true(即已經訪問)，將其未訪問過的鄰接點加進入隊列，則 <—[V4 V5 V6 V7]

☐取出V4，並標記為true(即已經訪問)，將其未訪問過的鄰接點加進入隊列，則 <—[V5 V6 V7 V8]

☐取出V5，並標記為true(即已經訪問)，因為其鄰接點已經加入隊列，則 <—[V6 V7 V8]

☐取出V6，並標記為true(即已經訪問)，將其未訪問過的鄰接點加進入隊列，則 <—[V7 V8]

☐取出V7，並標記為true(即已經訪問)，將其未訪問過的鄰接點加進入隊列，則 <—[V8]

☐取出V8，並標記為true(即已經訪問)，將其未訪問過的鄰接點加進入隊列，則 <—[]

　　廣度優先搜索的代碼

#include <queue>
using namespace std;
....
void BFSTraverse(Graph G)
{
    for (int v=0;v<G.vexnum;v++) //先將其所有頂點都設為未訪問狀態
        visited[v]=false;
    queue<int> Q;
    for(int v=0;v<G.vexnum;v++)    
    {
        if(visited[v]==false)   //若該點沒有訪問
        {
            Q.push(v);　　　　//將其加入到隊列中
            visited[v]=true;
            while (!Q.empty())　　//只要隊列不空，遍歷就沒有結束
            {
                int t =Q.front();　　//取出對頭元素
                Q.pop();
                printf(" %d ",t+1);  
                for(int j=0;j<G.vexnum;j++) //將其未訪問過的鄰接點加進入隊列
                    if(G.arcs[t][j]==1&&visited[j]== false)
                    {
                        Q.push(j);
                        visited[j]=true; //在這裡要設置true，因為這裡該頂點我們已經加入到了隊列，為了防止重復加入！
                    }
            }
        }
    }
}

 兩種算法的復雜度分析

　　深度優先

　　　　數組表示：查找所有頂點的所有鄰接點所需時間為O(n²)，n為頂點數，算法時間復雜度為O(n²) 　　

　　廣度優先

　　　　數組表示：查找每個頂點的鄰接點所需時間為O(n²)，n為頂點數，算法的時間復雜度為O(n²)