Contents

#include <stdio.h>
#include <queue>
using namespace std;

#define MAXVEX 100                      //最大顶点数,应由用户定义
#define INFINITY 65535                  //用65535来代表∞

bool visited[MAXVEX];                    //访问标志数组
typedef char VertexType;                 //顶点类型应用户定义
typedef int  EdgeType;                   //边上的权值应由用户定义
typedef int InforType;                   //信息的类型由用户定义

typedef struct Graph{
    VertexType vexs[MAXVEX];            //顶点表
    EdgeType arc[MAXVEX][MAXVEX];       //邻接矩阵,可看作边
    int numVertexes, numEdge;           //图中当前的顶点数和边数
}Graph;

//邻接矩阵的广度遍历算法
void BFS(Graph g){

    int i, j;
    queue <int> q;
    for(i = 0; i < g.numVertexes; i++)
        visited[i] = false;
    for(i = 0; i < g.numVertexes; i++)
    {
        if(!visited[i])                 //若是未访问过
        {
            visited[i] = true;
            printf("%c ", g.vexs[i]);   //打印结点，也可以其他操作
            q.push(i);
            while(!q.empty())
            {
                int m = q.front;
                q.pop();
                for(j = 0; j < g.numVertexes; j++)
                {
                    if(g.arc[m][j] == 1 && !visited[j])//如果有边,找到邻接点j,且没有访问过j结点
                    {
                        visited[j] = true;
                        printf("%c ", g.vexs[j]);
                        q.push(j);

                    }
                }
            }
        }
    }
}