【資料結構】圖的周遊方法 深度優先周遊和廣度優先周遊

接着上次的文章“圖的建構（鄰接連結清單法）”，鄰接連結清單法建構圖相對來說比較簡單，并且周遊起來也相對簡單，但是要是動态添加圖的節點和圖的邊，則是實在不友善，不過現在不管那麼多，今天的主題是周遊。 

- 有另外一種圖的建構方法，叫做十字連結清單法，插入删除比較友善，但是相對來說比較複雜，改天閑着木事的再搞。（其實主要原因是因為三四年前寫的代碼，現在翻出來了，現成的，尼瑪現在讓我從頭寫那麼複雜的資料結構，死的心都有了，是以還是等哪天心情好了，無聊了再寫十字連結清單吧）

上篇：圖的建構（鄰接連結清單法）http://blog.csdn.net/sundong_d/article/details/44983671

本次接着上一篇的講，圖的周遊就是從圖中的某一個頂點除法訪遍圖中的其餘頂點，并且使每一個頂點僅被通路一次。圖的周遊算法是求解圖的連通性問題、拓撲排序和求解關鍵路徑等算法的基礎
           

深度優先周遊

假設一個圖，圖中的所有頂點都未曾被通路，則深度優先周遊是從圖中的某一個頂點v出發，通路此頂點，然後找到與v鄰接的并且未被通路的點m出發通路，然後從m的未被通路的鄰接點n出發通路，再從那個點n的未被通路的鄰接點出發通路，出發......通路......，循環下去，直至圖中所有的和v與路徑想通的頂點都被通路到；若此時圖中還有頂點沒有被通路，則另選圖中的一個未曾被通路的頂點做起始點，重複上述過程，直到圖中的所有頂點都被通路到為止。此處不太好用語言描述，不知道各位看官看明白沒有，反正我沒糊塗。
下面上個圖（截圖截人家的，自己懶的畫，但是能講明白就好，黑貓、白貓，逮到耗子就是好貓）：

        
  
               

周遊過程：
以圖(a)中的G4為例，深度優先周遊圖的過程如圖(b)所示。假設從頂點出發進行搜尋，在通路了頂點v1之後，選擇鄰接點v2。因為v2未曾通路，則從v2出發進行搜尋，以此類推，接着從v4，v8，v5出發盡心搜尋。在通路了v5之後，由于v5的鄰接點都被通路，則回到v8。然後......就這樣一直回到v1，然後又從v1搜尋v3，如此進行下去。由此的發哦的通路序列為：
v1-->v2-->v4-->v8-->v5-->v3-->v6-->v7
當然，也可以在首先通路圖中任何一個點，那樣就會有不通過的通路序列。
注：圖(c)是廣度優先周遊的示意圖。
接下來是代碼，C++實作，其實也可以用其他語言寫，道理都是想通的，隻不過實作的方式不同
           

//----------------深度優先周遊--------------------//
//接上篇，上篇中以一個數組存儲所有圖中的頂點，是以如今通路時，可以用索引來标記該頂點是否被通路。
bool visited[MAX_VERTEX_NUM]; //通路标志數組，通過該數組表示頂點是否已通路，當visited[i]為false時，表示點i并未被通路。
int FirstAdjVex(ALGraph &G,int v) //找到在圖G中的，與頂點G.vertices[v]相鄰的未曾被通路的鄰接點
{
    int i;
    int n=-;
    ArcNode*p;
    p=G.vertices[v].firstarc;
    if(p)
    {
        i=p->adjvex;
        if(visited[i]==false)
            n=i;
    }
    return n;
}
int NextAdjVex(ALGraph &G,int v)//功能與上面的函數類似，可以優化，合并為一個函數，但是。。。。我懶！
{
    int i;
    int n=-;
    ArcNode *p;
    p=G.vertices[v].firstarc;
    for(i=p->adjvex;i<G.vexnum,p!=NULL;)
    {       
        i=p->adjvex;
        if(visited[i]==false)
        { 
            n=i;
            break; 
        }
        else
            p=p->nextarc;
    }
    return n;
}
void VisitFuc(ALGraph &G,int v) //通路輸出
{
    cout<<G.vertices[v].date<<" ";
}
void DFS(ALGraph &G,int v)//對圖G做深度優先周遊，周遊點從索引為v的頂點開始
{
    int w;
    visited[v]=true; //設定索引為v的頂點為已通路
    VisitFuc(G,v);  //通路索引為v的頂點
    //核心：循環遞歸，慢慢揣摩，找到v的未曾通路的一個鄰接點，通路；
    //然後找到v的未曾通路的另一個鄰接點通路，直至v的所有鄰接點都被通路為止
    for(w=FirstAdjVex(G,v);w>=;w=NextAdjVex(G,v))
        if(!visited[w]) DFS(G,w);//遞歸調用DFS
}
void DFSTraverse(ALGraph &G) //深度優先周遊的起始函數，調用此函數開始周遊。
{
    int v;
    for(v=;v<G.vexnum;v++) 
        visited[v]=false;//初始化，所有點都為被通路，統統設為false
    cout<<"深度優先搜尋："<<endl;
    for(v=;v<G.vexnum;v++) //確定周遊所有的點
    {
        if(!visited[v])//如果未被通路
            DFS(G,v);//對該頂點v調用DFS方法
    }
}
           

廣度優先周遊

廣度優先周遊是按照圖的層次結構周遊的過程。
簡單了解就是通路圖中的一個點之後，一次通路v的各個未曾通路過的鄰接點，然後分别從這些鄰接點出發，依次通路它們的鄰接點，并且使“先被通路的頂點的鄰接點”先于“後被通路的頂點的鄰接點”被通路。就像向湖面投一粒石子，激起一層的波紋。我們通路一個點，先把這個點的所有未被通路的鄰接點依次全部通路，然後再在已經通路的的鄰接點中找到那個最早被通路的點，從這個點出發，通路這個點所有未被通路的鄰接點，如此循環下去。
如圖(c)(此圖在上面深度優先周遊的那個圖裡面)，是對圖G4進行廣度優先周遊。沙鷗縣通路v1和v1的鄰接點v2和v3，然後依次通路v2的鄰接點v4和v5及v3的鄰接點v6和v7，最後通路v4的鄰接點v8。由于這些頂點的鄰接點均已經被通路，并且圖中所有頂點都被通路，由此完成了圖的周遊。
頂點通路序列：v1-->v2-->v3-->v4-->v5-->v6-->v7-->v8
和深度優先周遊類似，我們在周遊過程中需要一個通路标志數組。并且，為了順序通路路徑長度為2、3、...的頂點，需要附設隊列以存儲已經被通路的路徑長度為1，2...的頂點。
上代碼：
           

//----------------廣度優先周遊--------------------//

void BFSTraverse(ALGraph &G)
{
    int v;
    int w;
    queue<int> q; //STL隊列
    for(v=;v<G.vexnum;v++)
        visited[v]=false; //初始化，标記數組設定為false
    cout<<"廣度優先搜尋：";
    for(v=;v<G.vexnum;v++)
    {
        if(!visited[v])//如果未曾被通路
        {
            visited[v]=true;//标記為已通路
            VisitFuc(G,v); //通路該點
            q.push(v);   //v進隊
            //此處用隊列的含義：每次通路一個點，把該點入隊，當對這個點進行了廣度優先周遊，也就是所有鄰接點都被通路了，該點就出隊
            //是以，當對列不為空時，說明還有頂點沒有被進行廣度優先周遊。需要繼續
            while(q.empty()!=true)//當q不為空
            {
                v = q.front();
                q.pop();//出隊
                //w為v的尚未通路的鄰接點
                for(w=FirstAdjVex(G,v);w>=;w=NextAdjVex(G,v))//依次通路v的所有為被通路的鄰接點
                {   if(!visited[w])
                    {
                        visited[w]=true;
                        VisitFuc(G,w);
                        q.push(w);
                    }
                }
            }
        }
    }
}
           

好了，圖的兩種周遊方法講完了，下面貼上整個工程的代碼，代碼中是沒有這麼多注釋的，當有看不懂的時候，參考上一篇部落格和本篇部落格中對程式的注釋

#include<iostream>
#include<string>
#include<queue>
using namespace std;
#define ERROR 1
#define MAX_VERTEX_NUM 100
typedef struct ArcNode{
    int adjvex;
    struct ArcNode *nextarc;
    string info;
}ArcNode;
typedef struct VNode{
    char date;
    ArcNode * firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
    AdjList vertices;
    int vexnum,arcnum;        //目前圖的vexnum頂點數和arcnum弧數
    int kind;
}ALGraph;
int LocateVex(ALGraph &G,char &v1)
{
    int i;
    for(i=;i<G.vexnum;i++)
    {
        if(G.vertices[i].date==v1)
            return i;
    }
    if(i>=G.vexnum)
        return ERROR;
    else 
        return ;
}
void CreateDG(ALGraph &G)
{
    ArcNode *p,*q;
    char v1,v2;
    char v;
    int i,j,k,n;
    cout<<"請輸入圖的頂點數和弧數："<<endl;
    cin>>G.vexnum;
    cin>>G.arcnum;
    cout<<"請輸入頂點："<<endl;

    for(i=;i<G.vexnum;i++)
    {
        cin>>v;
        G.vertices[i].date=v;
        G.vertices[i].firstarc=NULL;
    }
    cout<<"請輸入弧尾和弧頭：";
    for(k=;k<G.arcnum;k++)
    {
        cin>>v1;
        cin>>v2;
        i=LocateVex(G,v1);j=LocateVex(G,v2);

        if(G.vertices[i].firstarc==NULL)
        {
            p=(ArcNode *)new ArcNode;
            G.vertices[i].firstarc=p;
            q=G.vertices[i].firstarc;
        }
        else
        {
            q=G.vertices[i].firstarc;
            for(n=;n<G.arcnum;n++,q=q->nextarc)
            {
                if(!q->nextarc)
                    break;
            }
            p=(ArcNode *)new ArcNode;
            q->nextarc=p;
            q=q->nextarc;
        }
        q->adjvex=j;
        q->nextarc=NULL;    
    }
    cout<<"圖建構成功！";
}
//----------------深度優先周遊--------------------//

bool visited[MAX_VERTEX_NUM];
int FirstAdjVex(ALGraph &G,int v)
{
    int i;
    int n=-;
    ArcNode*p;
    p=G.vertices[v].firstarc;
    if(p)
    {
        i=p->adjvex;
        if(visited[i]==false)
            n=i;
    }
    return n;
}
int NextAdjVex(ALGraph &G,int v)
{
    int i;
    int n=-;
    ArcNode *p;
    p=G.vertices[v].firstarc;
    for(i=p->adjvex;i<G.vexnum,p!=NULL;)
    {       
        i=p->adjvex;
        if(visited[i]==false)
        { 
            n=i;
            break; 
        }
        else
            p=p->nextarc;
    }
    return n;
}

void VisitFuc(ALGraph &G,int v)
{
    cout<<G.vertices[v].date<<" ";
}
void DFS(ALGraph &G,int v)
{
    int w;
    visited[v]=true;
    VisitFuc(G,v);  
    for(w=FirstAdjVex(G,v);w>=;w=NextAdjVex(G,v))
        if(!visited[w]) DFS(G,w);

}
void DFSTraverse(ALGraph &G)
{
    int v;
    for(v=;v<G.vexnum;v++)
        visited[v]=false;
    cout<<"深度優先搜尋："<<endl;
    for(v=;v<G.vexnum;v++)
    {
        if(!visited[v])
            DFS(G,v);
    }
}
//----------------廣度優先周遊--------------------//

void BFSTraverse(ALGraph &G)
{
    int v;
    int w;
    queue<int> q; //STL隊列
    for(v=;v<G.vexnum;v++)
        visited[v]=false;
//  InitQueue(Q);
    cout<<"廣度優先搜尋：";
    for(v=;v<G.vexnum;v++)
    {
        if(!visited[v])
        {
            visited[v]=true;
            VisitFuc(G,v);

            q.push(v);   //v進隊

            while(q.empty()!=true)
            {
                v = q.front();
                q.pop();
                for(w=FirstAdjVex(G,v);w>=;w=NextAdjVex(G,v))
                {   if(!visited[w])
                    {
                        visited[w]=true;
                        VisitFuc(G,w);

                        q.push(w);
                    }
                }
            }
        }
    }
}
/
void menu()
{
    cout<<'\n';
    cout<<" //---------------圖的基本操作---------------//"<<endl;
    cout<<"  **     1、圖的建構                        **"<<endl;
    cout<<"  **     2、深度優先周遊                    **"<<endl;
    cout<<"  **     3、廣度優先周遊                    **"<<endl;
    cout<<"  --------------------------------------------"<<endl;
    cout<<"請輸入數字進行選擇："<<endl;
}
int main()
{
    ALGraph G;
    int i;
    menu();
    cin>>i;
    while(i<)
    {
        switch(i)
        {
        case :CreateDG(G);break;
        case :DFSTraverse(G);cout<<endl;break;
        case :BFSTraverse(G);cout<<endl;break;
        default:return ERROR;
        }
        menu();
        cin>>i;
    }
    return ;
}