No.5.2 图的广度优先遍历
重温一遍 No.4.3 层层递进-广度优先搜索：https://www.cnblogs.com/yalimy/p/15021065.html
/* No.1 广度优先搜索，只找出最短路径层数即可
struct node{
int x; //当前节点
int y; //层数
};
struct node que[100];
int head=1,tail=1;
int n,m,start,stop;
int cur;
int flag=0;
int a[100][100],book[10]={0};
int main(){
int i,j;
int x,y;
scanf("%d %d %d %d",&n,&m,&start,&stop);
//初始化图的二维矩阵
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i==j) a[i][j]=0;
else a[i][j]=-1;
}
for(i=1;i<=m;i++){ //无向图，对称矩阵
scanf("%d %d",&x,&y);
a[x][y]=1;
a[y][x]=1;
}
que[head].x=start;
que[head].y=0;
tail++;
book[start]=1;
while(head
for(i=1;i<=n;i++){
if(a[cur][i]==1 && book[i]==0){
book[i]=1;
que[tail].x=i;
que[tail].y=que[head].y+1;
tail++;
if(i==stop){
flag=1;
break;
}
}
}
if(flag==1){
break;
}
head++;
}
printf("%d",que[tail-1].y);
getchar();getchar();return 0;
}
*/
/* No2. 广度优先算法：打印最短路径
struct node{
int x; //当前节点
int y; //父节点值
int s; //步数
};
struct node que[100];
int head=1,tail=1;
int n,m,start,stop;
int cur,hd;
int flag=0;
int a[100][100],book[10]={0};
int main(){
int i,j;
int x,y;
scanf("%d %d %d %d",&n,&m,&start,&stop);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i==j) a[i][j]=0;
else a[i][j]=-1;
}
for(i=1;i<=m;i++){
scanf("%d %d",&x,&y);
a[x][y]=1;
a[y][x]=1;
}
que[head].x=start;
que[head].y=0;
que[head].s=0;
tail++;
book[start]=1;
hd=head; //使用临时变量，防止 que[head] 真的被释放
while(head
for(i=1;i<=n;i++){
if(a[cur][i]==1 && book[i]==0){
book[i]=1;
que[tail].x=i;
que[tail].y=que[cur].x;
que[tail].s=que[cur].s+1;
tail++;
if(i==stop){
flag=1;
break;
}
}
}
if(flag==1){
break;
}
hd++; //指针前移
}
printf("最少遍历次数：%d\n",que[tail-1].s);
printf("遍历节点如下：\t");
for(i=head;i
printf("\n最短路径为：(%d,%d,%d)\t",que[tail-1].x,que[tail-1].y,que[tail-1].s);
cur=tail-1;
for(i=cur-1;i>=head;i--){
if(que[i].x==que[cur].y && que[i].s==que[cur].s-1){
printf("(%d,%d,%d)\t",que[i].x,que[i].y,que[i].s);
cur=i; //通过 cur 实现自我递归！
}
else
continue;
}
getchar();getchar();return 0;
}
*/
/* No3. 广度优先算法：打印最短路径
struct node{
int x; //当前节点
int y; //指向父节点所在队列的索引位置
int s; //步数
};
struct node que[100];
int head=1,tail=1;
int n,m,start,stop;
int cur,hd;
int flag=0;
int a[100][100],book[10]={0};
int main(){
int i,j;
int x,y;
scanf("%d %d %d %d",&n,&m,&start,&stop);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i==j) a[i][j]=0;
else a[i][j]=-1;
}
for(i=1;i<=m;i++){
scanf("%d %d",&x,&y);
a[x][y]=1;
a[y][x]=1;
}
que[head].x=start;
que[head].y=0;
que[head].s=0;
tail++;
book[start]=1;
hd=head;
while(head
for(i=1;i<=n;i++){
if(a[cur][i]==1 && book[i]==0){
book[i]=1;
que[tail].x=i;
que[tail].y=hd; //父节点所在队列的索引下标
que[tail].s=que[cur].s+1;
tail++;
if(i==stop){
flag=1;
break;
}
}
}
if(flag==1){
break;
}
hd++;
}
printf("最少遍历次数：%d\n",que[tail-1].s);
printf("遍历节点如下：\t");
for(i=head;i
printf("\n最短路径为：(%d,%d,%d)\t",que[tail-1].x,que[tail-1].y,que[tail-1].s);
cur=tail-1;
while(cur>head){ //注意，这里是大于head！
cur=que[cur].y; //直接找到父节点的索引坐标
printf("(%d,%d,%d)\t",que[cur].x,que[cur].y,que[cur].s);
}
getchar();getchar();return 0;
}
*/