深度广度遍历搜索的定义想必大家都能熟练的掌握了，下面我就通过一个图的实例，把应用的代码直接贴上供大家参考，以后可以直接借鉴或者使用。

#include <iostream>   

#include <string>   

#include "Queue.h"   

using namespace std;  

//图的邻接矩阵存储表示   

#define INFINITY INT_MAX   

#define MAX_VERTEX_NUM 20   

typedef enum {DG, DN, UDG, UDN} GraphKind; //{有向图，有向网，无向图，无向网}   

typedef enum {OK, ERROR} Status;  

typedef struct ArcCell{  

    int adj;        //顶点关系类型。对于无权图，用0或1表示相邻否。对于有权图，则为权值类型。   

    string info;    //该弧所携带的信息   

}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  

typedef struct {  

    int vexs[MAX_VERTEX_NUM];   //顶点向量   

    AdjMatrix arcs;             //邻接矩阵   

    int vexnum, arcnum;         //图的当前顶点数和弧数   

    GraphKind kind;             //图的种类标志   

}MGraph;  

bool visited[MAX_VERTEX_NUM];   //设访问标志数组，供遍历时使用  

2. 构造测试用的建立无向图的函数

[cpp] view plaincopyprint?

void CreateUDGTest(MGraph &G)  

{   //构造一个测试用的无向图   

    int i,j;  

    //数组a[9][2]包含所有边   

    //int a[9][2] = {0,1,0,2,0,3,1,4,1,5,4,5,7,8,8,9,9,7};   

    int a[9][2] = { {0,1}, {0,2}, {0,3}, {1,4}, {1,5}, {4,5}, {7,8}, {8,9}, {9,7}};  

    G.kind = UDG;  

    G.vexnum = 10;  

    G.arcnum = 9;  

    for(i=0; i<G.vexnum; ++i)        //构造顶点向量   

        G.vexs[i] = i;  

    for(i=0; i<G.vexnum; ++i)        //初始化为全0   

        for(j=0; j<G.vexnum; ++j)  

            G.arcs[i][j].adj = 0;         

    for(i=0; i<G.arcnum; ++i)        //对存在的边赋值1   

        G.arcs[a[i][0]][a[i][1]].adj = G.arcs[a[i][1]][a[i][0]].adj = 1;  

}   

3. 深度优先遍历和广度优先遍历函数

void DFSTraverse(MGraph G)  

{   //对图G作深度优先遍历   

    int v;  

    for(v=0; v<G.vexnum; ++v)    //访问标志数组初始化   

        visited[v] = false;  

    for(v=0; v<G.vexnum; ++v)  

        if(!visited[v])         //对未访问的顶点调用DFS   

            DFS(G, v);  

}  

void DFS(MGraph G, int v)  

{   //从第v个顶点出发，递归地深度优先遍历图G   

    int w;  

    visited[v] = true;  

    VisitFunc(v);               //访问第v个顶点   

    for(w = FirstAdjVex(G,v); w>=0; w=NextAdjVex(G, v, w))  

        if(!visited[w])  

            DFS(G, w);          //对v的尚未访问的邻接顶点w递归调用DFS   

}  

void BFSTraverse(MGraph G)  

{  

    //按广度优先非递归地遍历图G。使用辅助队列Q和访问标志数组visited   

    int v, w, u;  

    LinkQueue Q;  

    for(v=0; v<G.vexnum; ++v)    //访问标志数组初始化   

        visited[v] = false;  

    InitQueue(Q);               //置空的辅助队列   

    for(v=0; v<G.vexnum; ++v)  

        if(!visited[v])  

        {  

            visited[v] = true;  

            VisitFunc(v);  

            EnQueue(Q,v);  

            while(QueueEmpty(Q) == FALSE){  

                DeQueue(Q, u);  //对头元素出队，并置为u   

                for(w = FirstAdjVex(G,v); w>=0; w=NextAdjVex(G, v, w))  

                    if(!visited[w]){    //w为u未访问的邻接顶点   

                        visited[w] = true;  

                        VisitFunc(w);  

                        EnQueue(Q, w);  

                    }  

            }  

        }//if   

}//BFSTraverse   

void VisitFunc(int v)  

{   //访问第v个节点   

    cout<<v<<endl;  

}  

int FirstAdjVex(MGraph G, int v)  

{   //返回节点v的第一个邻接顶点   

    int i;  

    for(i=0; i<G.vexnum; ++i)  

        if(G.arcs[v][i].adj != 0 && i!=v)  

            return i;  

    return -1;          //如果没有，返回-1   

}  

int NextAdjVex(MGraph G, int v, int w)  

{  

    //返回节点v的邻接顶点中w之后的下一个邻接顶点   

    int i;  

    for(i=w+1; i<G.vexnum; ++i)  

        if(G.arcs[v][i].adj != 0 && i!=v)  

            return i;  

    return -1;          //如果没有，返回-1   

}   

4. 主函数-测试用

int main()  

{  

    MGraph gra;  

    CreateUDGTest(gra);             //构造无向图G   

    cout<<"对无向图G作深度优先遍历："<<endl;  

    DFSTraverse(gra);               //对无向图G作深度优先遍历   

    cout<<"对无向图G作广度优先遍历："<<endl;  

    BFSTraverse(gra);  

    return 0;  

}  

数据结构-6-深度广度遍历搜索原理详解