广度（宽度）优先搜索：队列

上一章详细的写出了深度优先遍历的四种情况的程序：
http://blog.csdn.net/zscfa/article/details/75947816

这一次来详细说说广度优先遍历：
广度优先搜索类似于二叉树的层序遍历，它的基本思想就是：首先访问起始顶点v，接着由v出发，依次访问v的各个未访问过的邻接顶点w1，w2，…，wi，然后再依次访问w1，w2，…，wi的所有未被访问过的邻接顶点；再从这些访问过的顶点出发，再访问它们所有未被访问过的邻接顶点……依次类推，直到图中所有顶点都被访问过为止。

二、BFS算法的实现

与树相比，图的不同之处在于它存在回路/环，因此在遍历时一个顶点可能被访问多次。为了防止这种情况出现，我们使用一个访问标记数组visited[]来标记顶点是否已经被访问过。
在广度优先搜索一个图之前，我们首先要构造一个图，图的存储方式主要有两种：邻接矩阵、邻接表。

与上次一样，我们来分类说明

（一）、队列的方式实现
1、邻接矩阵

#include<iostream>
#include<stdlib.h>
#include<queue>

#define MAX 100

using namespace std;

int visited[MAX];//用来记录顶点是否被标志

typedef struct
{
    char ves[MAX];//图的顶点信息
    int vester;//顶点的数目
    int edge;//边的数目
    int e[MAX][MAX];//图的边的信息

}MGraph;

void creatMGraph(MGraph *G)
{
    cout<<"please input the ves and edge:"<<endl;
    cin>>G->vester>>G->edge;

    int i;
    int j;
    int start;
    int end;
//初始化
    for(i = 0; i < G->vester; i++)
    {
        for(j = 0; j < G->vester; j++)
    {
        G->e[i][j] = 0;
    }
        visited[i] = 0;
    }

    cout<<"please input the edge,(vi,vj)"<<endl;
    for(i = 0; i < G->edge; i++)
    {
        cin>>start>>end;
    G->e[start][end] = 1;//构建无向图
    G->e[start][end] = 1;
    }
}
/*主要思想：被访问过的点压入队列,*/

void BFS(MGraph* G,int i)
{
    int k;
    int j;

    queue<int> q;

    visited[i] = 1;//标志顶点i已经被访问了
    cout<<i;

    q.push(i);

    while(!q.empty())
    {
        k = q.front();
    q.pop();

    for(j = 1; j < G->vester; j++)
    {
        if(G->e[k][j] != 0 && visited[j] != 1)
        {
    cout<<"k = "<<k<<endl;
            cout<<j<<endl;;
        visited[j] = 1;
        q.push(j);
        }
    }
    }
}

int main()
{
//    MGraph G = (MGraph*)malloc(MGraph);
    MGraph G;
    creatMGraph(&G);

    BFS(&G,0);

    return 0;
}

结果：

2、邻接表

#include<iostream>
#include<stdlib.h>
#include<queue>

#define MAX 100

using namespace std;

int visited[MAX] = {0};

struct Node// 边表结点
{
    int adjves;//存储顶点的下标
    struct Node* next;//连接下一个邻点
};

typedef struct Node EdgeNode;

typedef struct VertexNode//顶点表结点
{
    int ves;//顶点的值
    EdgeNode* firstedge;//相连的顶点的值
}VertexNode,AdjList[MAX];

typedef struct
{
    AdjList adjlist;//邻接表
    int ves;//顶点
    int edge;//边
}MGraph;

void createMGraph(MGraph *G)
{
    int i;
    int start;
    int end;

    EdgeNode *e;

    cout<<"please input the ves and edge:"<<endl;
    cin>>G->ves>>G->edge;
//初始化
    cout<<"please input the ves:"<<endl;

    for(i = 0; i < G->ves; i++)//输入顶点
    {
        cin>>G->adjlist[i].ves;
    G->adjlist[i].firstedge = NULL;
    }
//创建邻接矩阵

    cout<<"please input the edges:"<<endl;;
    for(i = 0; i < G->edge; i++)
    {
        cin>>start>>end;

        e =(EdgeNode*)malloc(sizeof(EdgeNode));//分配空间
    e->adjves = end;
    e->next = G->adjlist[start].firstedge;
    G->adjlist[start].firstedge = e;//类似于链表的前插

        e =(EdgeNode*)malloc(sizeof(EdgeNode));//分配空间
    e->adjves = start;
    e->next = G->adjlist[end].firstedge;
    G->adjlist[end].firstedge = e;//类似于链表的前插
    }
}
void bfs(MGraph *G)
{
    int i;
    int k;

    EdgeNode* p;

    queue<int> q;

    for(i = 0; i < G->ves; i++)
    {
        visited[i] = 0;
    }
    for(i = 0; i < G->ves; i++)
    {
        if(visited[i] == 0)
    {
        visited[i] = 1;
        cout<<G->adjlist[i].ves;
        q.push(i);

        while(!q.empty())
        {
        k = q.front();
        q.pop();

        p = G->adjlist[k].firstedge;

        while(p)
        {
            if(visited[i] == 0)
            {
                visited[i] = 1;

                cout<<G->adjlist[p->adjves].ves;
            q.push(p->adjves);
            }
            p = p->next;
        }

        }
    }
    }
}
int main()
{
    MGraph G;
    createMGraph(&G);

    bfs(&G);
    return 0;
}

结果：