include[HTML_REMOVED]

using namespace std;

define MaxVex 100

typedef char VexType;
typedef int EdgeType;
typedef struct{
VexType node[MaxVex];
EdgeType edges[MaxVex][MaxVex];
int vexnum,edgenum;
}AdjMatrix;
//邻接矩阵定义

typedef struct EdgeNode{
int adjvex;//邻接点下标
struct EdgeNode *next;
}EdgeNode;//边结点定义

typedef struct VexNode{
VexType data;
EdgeNode * firstedge;
}VexNode;//图结点定义

typedef struct{
VexNode vertex[MaxVex];
int vexnum,edgenum;
}AdjList;//邻接表定义

int visited[MaxVex];

void bfs(AdjMatrix G,int n);

void bfs_main(AdjMatrix G){
for(int i=1;i<=G.vexnum;i) visited[i]=0;
for(int i=1;i<=G.vexnum;i){
if(visited[i]==0){
bfs(G,i);
}
}
}

void bfs(AdjMatrix G,int n){
int queue[MaxVex];
int front=0,rear=0;
visited[n]=1;//调试半天，我认为入队前进行访问和修改visited数组较好
cout<<n;
queue[rear]=n;
while(front<rear){
int p=queue[front];
for(int i=1;i<=G.vexnum;i){
if(G.edges[p][i]==1&&visited[i]==0){
visited[i]=1;
cout<<i;
queue[rear]=i;
}
}
}
}

int main(){
AdjMatrix G;
G.vexnum=9;
G.edgenum=10;
for(int i=1;i<=MaxVex-1;i){
for(int j=1;j<=MaxVex-1;j)
G.edges[i][j]=0;
}
G.edges[1][2]=1;G.edges[2][1]=1;
G.edges[1][4]=1;G.edges[4][1]=1;
G.edges[1][5]=1;G.edges[5][1]=1;
G.edges[2][4]=1;G.edges[4][2]=1;
G.edges[2][3]=1;G.edges[3][2]=1;
G.edges[3][6]=1;G.edges[6][3]=1;
G.edges[4][7]=1;G.edges[7][4]=1;
G.edges[5][7]=1;G.edges[7][5]=1;
G.edges[7][8]=1;G.edges[8][7]=1;
G.edges[8][9]=1;G.edges[9][8]=1;
cout<<”BFS”<<endl;
cout<<”124537689”<<endl;
bfs_main(G);
//邻接矩阵实现bfs
}