bfstraverse.cpp

c语言数据结构源代码（全）相当经典

//BFSTraverse.cpp
//广度优先遍历图
# include <iostream.h>
# include <malloc.h>
# include <conio.h>
# include <stdio.h>

# define MAXQSIZE 100
# define INFINITY 1000
# define MAX_VERTEX_NUM 20
# define OK 1
# define ERROR 0
typedef enum{DG,DN,UDG,UDN} GraphKind;
typedef int EType;
typedef int InfoType;
typedef int VertexType;
typedef int QElemType;

typedef struct ArcCell		//定义 MGraph
{  EType adj;
   InfoType *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct				
{  VertexType vexs[MAX_VERTEX_NUM];
   AdjMatrix  arcs;
   int vexnum,arcnum;
   GraphKind kind;
}MGraph;

typedef struct SqQueue		//定义 SqQueue
{    QElemType *base;
     int front;
     int rear;
}SqQueue;

int LocateVex(MGraph G,int v)	//确定v在G中的位置
{
	return(v);
}

int CreatUDN(MGraph &G)		//CreatUDN() 子函数
{  int i,j,k,v1,v2,w;
   int IncInfo;
   cout<<endl<<"Please input the number of G.vexnum 顶点数目 (eg, 4): ";
   cin>>G.vexnum;			//输入顶点数目
   cout<<"Please input the number of G.arcnum 弧的数目 (eg, 4): ";
   cin>>G.arcnum;			//输入弧的数目
   //cout<<"Please input IncInfo 弧的信息 (0 for none)                  : ";
   printf("Please input IncInfo 弧的信息 (0 for none)          : ");
   //cin>>IncInfo;			//输入弧的信息
   scanf("%d",&IncInfo);
   for(i=1;i<=G.vexnum;++i)
     for(j=1;j<=G.vexnum;++j)
       {  G.arcs[i][j].adj=INFINITY;	//初始化邻接矩阵
		  G.arcs[i][j].info=NULL;
       }
   cout<<"Plese input 弧 arc(V1-->V2), For example: arc(1,3),arc(2,4)..."<<endl;
   for(k=0;k<G.arcnum;++k)	//构造邻接矩阵
   {   cout<<endl<<"Please input the "<<k+1<<"th arc's v1 弧头 [1.."<<G.vexnum<<"] :";
       cin>>v1;				//输入弧头
       cout<<"Please input the "<<k+1<<"th arc's v2 弧尾 [1.."<<G.vexnum<<"] :";
       cin>>v2;				//输入弧尾
       cout<<"Please input the "<<k+1<<"th arc's weight 权      :";
       cin>>w;				//输入权
	   i=LocateVex(G,v1);	//确定v1在G中的位置
       j=LocateVex(G,v2);	//确定v2在G中的位置
       while(i<1||i>G.vexnum||j<1||j>G.vexnum)	//如果弧头或弧尾不合法,重新输入
       {	cout<<"Please input Again the "<<k+1<<"th arc's v1 弧头[1.."<<G.vexnum<<"] :";
			cin>>v1;
			cout<<"Please input Again the"<<k+1<<"th arc's v2 弧尾[11.."<<G.vexnum<<"] :";
			cin>>v2;
			cout<<"Please input Again the "<<k+1<<"th arc's weight 权      :";
			cin>>w;
			i=LocateVex(G,v1);	//确定v1在G中的位置
			j=LocateVex(G,v2);	//确定v2在G中的位置
       } //while end
       G.arcs[i][j].adj=w;			//weight
	   if(IncInfo!=0)
			{	G.arcs[i][j].info=&IncInfo;
			}
   } //for end
   return (OK);
} //CreatUDN() end

void ShowMGraph(MGraph G)	//输出图 G
{	int i,j;
	for(i=1;i<=G.vexnum;++i)
		for(j=1;j<=G.vexnum;++j)
			if(G.arcs[i][j].adj!=INFINITY)
				printf("\narc(%d,%d) weight=%d  ",i,j,G.arcs[i][j].adj);
}

int InitQueue(SqQueue &Q)	//InitQueue() 子函数,初始化队列
{   Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));
    if(!Q.base)
    {   cout<<endl<<"Overflow ! ";
		return (ERROR);
    }
    Q.front=Q.rear=0;
    return (OK);
} //InitQueue() end

int QueueEmpty(SqQueue Q)	//QueueEmpty 子函数,判断对列是否为空
{  if(Q.front==Q.rear)
      return (OK);
   else
      return (ERROR);
} //QueueEmpty() end

int EnQueue(SqQueue &Q,QElemType e)	//EnQueue() 子函数,入队
{   if((Q.rear+1)%MAXQSIZE==Q.front)	//if full
    {   cout<<"Errer ! The SqQeueu is full ! ";
		return 0;
    }
    Q.base[Q.rear]=e;
    Q.rear=(Q.rear+1)%MAXQSIZE;
    return (OK);
} //EnQueue() end

int DeQueue(SqQueue &Q,QElemType &e)	//DeQueue() 子函数,出队
{  if(Q.front==Q.rear)		//empty queue
   {    cout<<endl<<"Errer !  It's empty!";
		return 0;
   }
   e=Q.base[Q.front];
   Q.front=(Q.front+1)%MAXQSIZE;
   return (e);
} //DeQueue() end

void BFSTraverse(MGraph G)		//BFSTraverse() 子函数
//按广度优先非递归遍历图G.使用辅助队列Q和访问标志数组visited 
{  int v,w,u;
   int visited[MAX_VERTEX_NUM];	//访问标志数组
   SqQueue Q;
   for(v=1;v<=G.vexnum;++v)
      visited[v]=0;				//访问标志数组初始化
   InitQueue(Q);				//置空的辅助队列
   for(v=1;v<=G.vexnum;++v)
     if(visited[v]==0)			//v尚未访问
     {  visited[v]=1;
		cout<<v<<"-->";
		EnQueue(Q,v);			//v入队
		while(!QueueEmpty(Q))
		{   DeQueue(Q,u);		//队头元素出队并置为u
		    for(w=1;w<=G.vexnum;++w)
				if((G.arcs[u][w].adj!=INFINITY)&&(visited[w]!=1))
	         	{	visited[w]=1;
					cout<<w<<"-->";
					EnQueue(Q,w); 	//w入队
				} 
		} //while end
    } //if end
} //BFSTraverse() end


void main()				//main() 函数
{   MGraph G;
    cout<<endl<<endl<<"BFSTraverse.cpp";
    cout<<endl<<"================"<<endl;
    if(CreatUDN(G))		//调用 CreatUDN()
	{	//cout<<endl<<"Create MGraph success !";	//如果构造图成功,则输出图
		printf("\nCreate MGraph success !");
		ShowMGraph(G);	//显示构造成功后的图
	}
    cout<<endl<<endl<<"BFS Traverse is as follows :";
    cout<<endl<<"Begin->";
    BFSTraverse(G);		//调用 DFSTraverse()
	cout<<"end!"<<endl<<endl<<"...OK!...";
    getch();
} //main() end