圖論中DFS與BFS的差別、用法、詳解… DFS與BFS的差別、用法、詳解？

寫在最前的三點：

1、所謂圖的周遊就是按照某種次序通路圖的每一頂點一次僅且一次。

2、實作bfs和dfs都需要解決的一個問題就是如何存儲圖。一般有兩種方法：鄰接矩陣和鄰接表。這裡為簡單起

見，均采用鄰接矩陣存儲，說白了也就是二維數組。

一、深度優先搜尋周遊

① 通路v

② 依次從頂點v未被通路的鄰接點出發深度周遊。

2、一點心得：dfs算法最大特色就在于其遞歸特性，使得算法代碼簡潔。但也由于遞歸使得算法難以了解，原因

在于遞歸使得初學者難以把握程式運作到何處了！一點建議就是先學好遞歸，把握函數調用是的種種。

3、算法代碼：

#include  

using namespace std;  

int a[11][11];  

bool visited[11];  

void store_graph()  //鄰接矩陣存儲圖  

{  

    int i,j;  

    for(i=1;i<=10;i++)  

        for(j=1;j<=10;j++)  

            cin>>a[i][j];  

}  

void dfs_graph()    //深度周遊圖  

    void dfs(int v);  

    memset(visited,false,sizeof(visited));  

    for(int i=1;i<=10;i++)  //周遊每個頂點是為了防止圖不連通時無法通路每個頂點  

        if(visited[i]==false)  

            dfs(i);  

void dfs(int v)  //深度周遊頂點  

    int Adj(int x);  

    cout<<v<<" ";  //通路頂點v  

    visited[v]=true;  

    int adj=Adj(v);  

    while(adj!=0)  

    {  

        if(visited[adj]==false)     

            dfs(adj);      //遞歸調用是實作深度周遊的關鍵所在  

        adj=Adj(v);  

    }  

int Adj(int x)   //求鄰接點  

    for(int i=1;i<=10;i++)  

        if(a[x][i]==1 && visited[i]==false)  

            return i;  

    return 0;  

int main()  

    cout<<"初始化圖:"<<endl;  

    store_graph();  

    cout<<"dfs周遊結果:"<<endl;  

    dfs_graph();  

4、小測試

二、廣度優先搜尋周遊

1、從頂點v出發周遊圖G的算法買描述如下：

①通路v

②假設最近一層的通路頂點依次為vi1,vi2,vi3...vik，則依次通路vi1,vi2,vi3...vik的未被通路的鄰接點

③重複②知道沒有未被通路的鄰接點為止

裡用STL中的實作。該算法由于不是遞歸算法，是以程式流程是清晰的。

#include      

void store_graph()    

        for(int j=1;j<=10;j++)  

void bfs_graph()      

    void bfs(int v);  

    for(int i=1;i<=10;i++)    

            bfs(i);  

void bfs(int v)  

    queue<<span

class="datatypes" style="margin: 0px; padding: 0px; border: none;

color: rgb(46, 139, 87); background-color: inherit; font-weight:

bold;">int> myqueue;  

    int adj,temp;  

    cout<<v<<" ";  

    myqueue.push(v);  

    while(!myqueue.empty())    //隊列非空表示還有頂點未周遊到  

        temp=myqueue.front();  //獲得隊列頭元素  

        myqueue.pop();         //頭元素出對  

        adj=Adj(temp);  

        while(adj!=0)  

        {  

            if(visited[adj]==false)  

            {  

                cout<<adj<<" ";  

                visited[adj]=true;  

                myqueue.push(adj);   //進對  

            }  

            adj=Adj(temp);  

        }  

int Adj(int x)     

    cout<<"bfs周遊結果:"<<endl;  

    bfs_graph();  

4、小測試：