编辑代码

#include<stdio.h> 
#include<iostream> 
using namespace std;
#define MaxInt 32767     //表示极大值
#define  MVNum 100       //最大定点数 
#define OK 1
#define MAXQSIZE 100


typedef char VerTexType;   //假设顶点的数据类型为字符型
typedef int ArcType;       //假设边的权值类型为整型 


typedef struct
{
    VerTexType vexs[MVNum];    //定点表
    ArcType arcs[MVNum][MVNum];    //邻接矩阵
    int vexnum,arcnum;      //图的当前点和边数 
}AMGraph; 

AMGraph G;

typedef struct   
{  
    int *base;  
    int front,rear;   
}SqQueue;  

int InitQueue(SqQueue &Q)
{//构造一个空队列Q
    Q.base=new int[MAXQSIZE];    //为队列分配一个最大容量为MAXQSIZE的数组空间
    if(!Q.base) exit(0);        //存储分配失败
    Q.front=Q.rear=0;                  //头指针和尾指针为零，队列为空
    return OK;     
 }

int EnQueue(SqQueue &Q,int e)
 {//插入元素e为Q的新的队尾元素
     if((Q.rear+1)%MAXQSIZE==Q.front)   //尾指针在循环意义上加1后等于头指针，表明队满
        return 0;
    Q.base[Q.rear]=e;                //新元素插入队尾
    Q.rear=(Q.rear+1)%MAXQSIZE;       //队尾指针加1
    return OK; 
 }
 
int DeQueue(SqQueue &Q,int &e)
 {//删除Q的队头元素，用e返回其值
     if(Q.front==Q.rear) return 0;   //队空
    e=Q.base[Q.front];                  //保存队头元素
    Q.front=(Q.front+1)%MAXQSIZE;       //队头指针加1 
    return OK; 
     
 }

 
 int QueueEmpty(SqQueue &Q)
{
    if (Q.front==Q.rear)   return OK;
    else return 0; 
}

int LocateVex(AMGraph G,int b) 
{
    int a;
    for(a=0;a<G.vexnum;a++)   //判断顶点在第几个位置 
    {
        if(G.vexs[a]==b)  
        return a;
     }
 } 

int CreateUDN(AMGraph &G)
{//采用邻接矩阵表示法，创建无向网G
    cout<<"请输入顶点的个数：\n"; 
    cin>>G.vexnum;           //输入总顶点数
    cout<<"请输入边的条数：\n";
    cin>>G.arcnum;        //输入总边数 
    int i,j,k,v1,v2,w;
    cout<<"依次输入顶点的信息：\n";
    for(i=0;i<G.vexnum;i++)       //依次输入点的信息 
        cin>>G.vexs[i];
    for(i=0;i<G.vexnum;i++)       //初始化邻接矩阵，边的权值位置为极大值MaxInt 
        for(j=0;j<G.vexnum;j++)
            G.arcs[i][j]=0;
    for(k=0;k<G.arcnum;k++)        //构造邻接矩阵
    {
        cout<<"输入一条边依附的顶点:  ";
        cin>>v1>>v2;         //输入一条边依附的顶点及权值
//        i=LocateVex(G,v1);
//        j=LocateVex(G,v2);       //确定v1和v2在G中的位置，及顶点数组的下标
//        G.arcs[i][j]=w;          //变<v1，v2>的初值置为w
//        G.arcs[j][i]=G.arcs[i][j];    //置<v1，v2>的对称边<v2，v1>的权值为w 
        G.arcs[v1][v2]=1;
        G.arcs[v2][v1]=1;
     } 
     return OK; 
}

bool visited[MVNum];      //访问标志数组，其初值为“false”
void DFS_AM(AMGraph G,int v)
{//从第V个定点出发递归的深度优先遍历图G 
    cout<<v;
    int w; 
    visited[v]=1;      //访问第v个顶点，并置访问标志数组相应分量值为true
    for(w=1;w<=G.vexnum;w++) 
    if((G.arcs[v][w]!=0)&&(!visited[w]))
        DFS_AM(G,w);
}

void DFSTraverse(AMGraph G)
{//对非连接图G做深度优先遍历
    int v;
    for(v=0;v<G.vexnum;++v)     
        visited[v]=0;
    for(v=1;v<=G.vexnum;++v)
        if(!visited[v])   
        DFS_AM(G,v);      //对尚未访问的顶点调用DFS
     
}


void BFS(AMGraph G,int v) 
{//按广度优先非递归遍历连接图
    cout<<v;
    int u,w;
    SqQueue Q;
//    for(w=0;w<G.vexnum;w++)
//    {
//        visited[w]=0;
//    }
    visited[v]=1;
    InitQueue(Q);
    EnQueue(Q,v);
    while(!QueueEmpty(Q))
    {
        DeQueue(Q,u);
        for(w=1;w<=G.vexnum;w++)
            if((G.arcs[u][w]!=0)&&(!visited[w]))
            {
                cout<<w;
                visited[w]=1;
                EnQueue(Q,w);
            }
    }
    
}



int main() 
{ 
    CreateUDN(G);
    
    int choose,v;
    while(1)
    {    
        cout<<"请输入功能0（DFS）或1（BFS）:\n";
        cin>>choose;
        if(choose==0)
        {
            DFS_AM(G,1);
            break;
         } 
        else if(choose==1)
        {
            BFS(G,1);
            break;
        }
        else
        {
            cout<<"输入错误，请重新输入:\n";
        
        }        
    }
    
}