#include<stdio.h>
#include<stdlib.h>
#define Max_Nv 30 //最大顶点数
#define Max_Ne 30 //最大边数
#define MaxSize 100
bool visited[Max_Nv];
FILE *fo;
typedef struct MGraph{
int rec[Max_Nv][Max_Ne];
int Nv;
int Ne;
}MGraph;
typedef struct{
int *Data;
int rear;
int front;
}Queue;
MGraph Create(MGraph G,int Nv,int Ne,int *input){
int t=-1;
int i,j;
for(i=0;i<Nv;i++){
for(j=0;j<Ne;j++){
G.rec[i][j]=0;
}
}
for(int k=0;k<Ne;k++){
i=input[++t];
j=input[++t];
G.rec[i][j]=input[++t];
}
return G;
}
Queue CreateQ(){
Queue Q;
Q.Data=(int *)malloc(Max_Nv*sizeof(MGraph));
Q.rear=0;
Q.front=0;
return Q;
}
int isEmpty(Queue Q){
return (Q.rear == Q.front);
}
int isFull(Queue PtrQ){
return (PtrQ.rear+1)%MaxSize == PtrQ.front;
}
void EnQueue(Queue PtrQ,int item){
if(isFull(PtrQ)){
printf("队列满");
return;
}
PtrQ.rear=(PtrQ.rear+1)%MaxSize;
PtrQ.Data[PtrQ.rear]=item;
}
int DeleteQ(Queue PtrQ){
if(isEmpty(PtrQ)){
printf("队列空");
return -1;
}
else{
PtrQ.front=(PtrQ.front+1)%MaxSize;
return PtrQ.Data[PtrQ.front];
}
}
int First(MGraph G,int V){
for(int i=0;i<G.Nv;i++){
if(G.rec[V][i]!=0){
return i;
}
}
return -1;
}
int Next(MGraph G,int V,int k){
for(int i=k+1;i<G.Nv;i++){
if(G.rec[V][i]!=0) return i;
}
return -1;
}
void BFS(MGraph G,int V,FILE *fo){
visited[V]=true;
fprintf(fo,"V%d ",V);
Queue Q;
Q=CreateQ();
EnQueue(Q,V);
while(!isEmpty(Q)){
V=DeleteQ(Q);
for(int i=First(G,V);i<G.Nv;i=Next(G,V,i)){
if(!visited[i]){
visited[i]=true;
fprintf(fo,"V%d ",i);
EnQueue(Q,i);
}
}
}
}
int main(){
FILE *fp=fopen("D://input.txt","r");
FILE *fo=fopen("D://output1.txt","w");
int Nv,Ne,input[1000];
int n,num=0;
int visited[1000];
MGraph G;
while(fscanf(fp,"%d",&n)!=EOF){
num++;
if(n==-1) break;
else if(num==1) Nv=n;
else if(num==2) Ne=n;
else{
input[num-3]=n;
}
}
Create(G,Nv,Ne,input);
for(int i=3*Ne;i<num-3;i++){
for(int j=0;j<Nv;j++){
visited[j]=false;
}
fprintf(fo,"BFS From V%d:",input[i]);
BFS(G,input[i],fo);
fprintf(fo,"\n");
}
}
是一个图的广度优先探索遍历