广度优先遍历类似二叉树或者其他算法的层序遍历，一层一层的去搜索。
#include <stdio.h> typedef char VertexType typedef int edgetype #define Maxsize 100 typedef struct { VertexType vertex[Maxsize]; //定义一维数组来存储顶点 edgetype arc[Maxsize][Maxsize]; //二维数组保存连接状况 int vertex_num; //顶点数 int edge_num; //边数 } Mat_Grph; int visited[Maxsize] //定义一维数组，0表示没访问过，1表示访问过 int front = 0; int rear = 0; int queue[Maxsize]; //创建队头队尾和队数组 void create_graph(Mat_Grph *G){ //创建图 G->vertex_num = 9; G->edge_num = 15; G->vertex[0] = 'A'; G->vertex[1] = 'B'; G->vertex[2] = 'C'; G->vertex[3] = 'D'; G->vertex[4] = 'E'; G->vertex[5] = 'F'; G->vertex[6] = 'G'; G->vertex[7] = 'H'; G->vertex[8] = 'I'; for(int i = 0;i<G->vertex_num;i++){ for(int j = 0;j<G->vertex_num;j++){ G->arc[i][j] = 0; } } //先行覆盖二维数组为0 G->arc[0][1] = 1; G->arc[0][5] = 1; //A-B A-F G->arc[1][2] = 1; G->arc[1][6] = 1; G->arc[1][8] = 1; //B-C B-G B-I G->arc[2][3] = 1; G->arc[2][8] = 1; //C-D C-I G->arc[3][4] = 1; G->arc[3][6] = 1; G->arc[3][7] = 1; G->arc[3][8] = 1; //D-E D-G D-H D-I G->arc[4][5] = 1; G->arc[4][7] = 1; //E-F E-H G->arc[5][6] = 1; //F-G G->arc[6][7] = 1; //G-H for(int i = 0;i<G->vertex_num;i++){ for(int j = 0;j<G->vertex_num;j++){ G->arc[j][i] = G->arc[i][j]; //对称覆盖，因为是边双向的 } } void bfs(Mat_Grph G){ //bfs:breath first search int i = 0; visited[i] = 1; //更改状态为：已访问过 printf("%c\n",G->vertex[i]); queue[rear] = i; rear++; while(front!=rear){ i = queue[front]; front++; for(int k = 0;k<G->vertex_num;k++){ if(G->arc[i][k]==1&&visited[k]==0){ visited[k] = 1; printf("%c\n",G->vertex[k]); queue[rear] = k; rear++; } } } int main(){ Mat_Grph G; create_graph(&G); bfs(G); return 0; }
