【数据结构作业五】以邻接表作存储结构，广度遍历图的优先搜索序列

╰半橙微兮° 2022-06-03 23:19 96阅读 0赞

#include <iostream>
    #define MVNum 100
    #define MAXQSIZE 100
    using namespace std;
    typedef char ElemType;
    typedef int QElemType;
    typedef struct {
    	QElemType *base;
    	int front,rear;
    }SqQueue;
    typedef struct ArcNode
    {
    	int adjvex;
    	struct ArcNode *nextarc;
    }ArcNode;
    typedef struct 
    {
    	ElemType data;
    	ArcNode *firstarc;
    }VerNode;
    typedef  struct 
    {  VerNode  vertices[MVNum];
        int   vernum, arcnum;
    }ALGraph;
    int Locate(ALGraph G, ElemType v)
    {
    	for(int i=0;i<G.vernum;i++)
    	if(v==G. vertices[i].data)
    	return i;
    }
    bool InitQueue(SqQueue &Q)
    {
    	Q.base=new QElemType[MAXQSIZE];
    	if(!Q.base)
    	  return false;
    	Q.front=Q.rear=0;
    	return true;
    }
    bool EnQueue(SqQueue &Q,QElemType e)
    {
    	if((Q.rear+1)%MAXQSIZE==Q.front)
    	  return false;
    	Q.base[Q.rear]=e;
    	Q.rear=(Q.rear+1)%MAXQSIZE;
    	return true;
    }
    bool DeQueue(SqQueue &Q,QElemType &e)
    {
    	if(Q.front==Q.rear)
    	  return false;
    	e=Q.base[Q.front];
    	Q.front=(Q.front+1)%MAXQSIZE;
    	return true;
    }
    bool QueueEmpty(SqQueue Q)
    {
    	if(Q.front==Q.rear)
    	  return true;
    	else 
    	  return false;
    }
    void  CreateDG(ALGraph &G)
    {   int i,k,j;
        ElemType v1,v2;
        ArcNode *p;
        cout<<"请输入顶点数和边数:";
        cin>>G.vernum >>G.arcnum;
        for (i=0;i<G.vernum;i++)
          {
    	      cout<<"请输入顶点:";
    	      cin>>G. vertices[i].data;  //读入顶点
              G. vertices[i]. firstarc=NULL; 
          }    
        for (k=1;k<=G.arcnum;k++)
          {   
              cout<<"请输入一条边:";
    	      cin>>v1>>v2;  //读入一条弧
              i=Locate(G,v1);  j=Locate(G,v2);  //查找顶点在顶点表中的位置
              p=new ArcNode;  p->adjvex=j; 
              p->nextarc= G. vertices[i]. firstarc;
              G. vertices[i]. firstarc=p;
          }
    }
    int FirstAdjVex(ALGraph G,ElemType v)
    {
    
    	ArcNode *p=G. vertices[v]. firstarc;
    	if(p){
    		return p->adjvex;
    	}
    	else{
    		return -1;
    	}
    }
    int NextAdjVex(ALGraph G,ElemType v,ElemType w)
    {
     
    	ArcNode *p=G. vertices[v]. firstarc;
    	while(p){
    		if(p->adjvex==w) break;
    		p=p->nextarc;
    	}
    	if(!p||!p->nextarc){
    		return -1;
    	}
    	else{
    		return (p->nextarc)->adjvex;
    	}
    }
    bool  visited[MVNum]; 
    void BFS(ALGraph G,int v)
    {
    	SqQueue Q;
    	QElemType u;
    	int w;
    	InitQueue(Q);
    	cout<<G.vertices[v].data;
    	visited[v]=true;
    
    	EnQueue(Q,v);
    	while(!QueueEmpty(Q))
    	{
    		DeQueue(Q,u);
    		for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
    		if(!visited[w])
    		{
    			cout<<G.vertices[w].data;visited[w]=true;
    			EnQueue(Q,w);
    		}
    	}
    }
    void BFSTraverse(ALGraph G)
       {   int v;
           for (v=0;v<G.vernum;v++) 
                visited[v]=false;
               // BFS(G,v);
           for (v=0;v<G.vernum;v++) 
                if (!visited[v])      BFS(G,v); 
       }
    int main()
      { 
      	ALGraph G; 
      	CreateDG(G);
      	cout<<"该图的广度优先序列输出为:" ;
      	BFSTraverse(G);
       }