#include"stdio.h"
#include"stdlib.h"
#define INFINITY 32767 
#define MAX_VEX 20 //最大顶点个数 
#define QUEUE_SIZE (MAX_VEX+1) //队列长度 
bool *visited; //访问标志数组 
int z=1;       //图的邻接矩阵存储结构 
typedef struct{ 
char *vexs;    //顶点向量 
int arcs[MAX_VEX][MAX_VEX]; //邻接矩阵 
int vexnum,arcnum; //图的当前顶点数和弧数 
}Graph; 
class Queue{  //队列类  
public: 
void InitQueue(){ 
base=(int *)malloc(QUEUE_SIZE*sizeof(int)); 
front=rear=0; 
} 
void EnQueue(int e){ 
base[rear]=e; 
rear=(rear+1)%QUEUE_SIZE; 
} 
void DeQueue(int &e){ 
e=base[front]; 
front=(front+1)%QUEUE_SIZE; 
} 
int *base; 
int front; 
int rear; 
}; 
int Locate(Graph G,char c){ //图G中查找元素c的位置
for(int i=0;i<G.vexnum;i++) 
if(G.vexs[i]==c) return i; 
return -1; 
} 
void CreateUDN(Graph &G){  //创建无向网
int i,j,w,s1,s2; 
char a,b,c,temp; 
printf("输入顶点数和弧数:"); 
scanf("%d%d",&G.vexnum,&G.arcnum); 
temp=getchar();    //接收回车 
G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配顶点数目 
printf("输入%d个顶点.\n",G.vexnum); 
for(i=0;i<G.vexnum;i++){ //初始化顶点 
scanf("%c",&G.vexs[i]); 
temp=getchar(); //接收回车 
} 
for(i=0;i<G.vexnum;i++) //初始化邻接矩阵 
for(j=0;j<G.vexnum;j++) 
G.arcs[i][j]=INFINITY; 
printf("输入%d条弧.\n",G.arcnum); 
for(i=0;i<G.arcnum;i++){ //初始化弧 
printf("输入弧%d:  ",i);
scanf("%c %c %d%c",&a,&b,&w,&c); //输入一条边依附的顶点和权值 
s1=Locate(G,a); 
s2=Locate(G,b); 
G.arcs[s1][s2]=G.arcs[s2][s1]=w; 
} 
} 
int FirstVex(Graph G,int k){ //图G中顶点k的第一个邻接顶点
if(k>=0 && k<G.vexnum){ //k合理 
for(int i=0;i<G.vexnum;i++) 
if(G.arcs[k][i]!=INFINITY) return i; 
} 
return -1; 
} 
//图G中顶点i的第j个邻接顶点的下一个邻接顶点
int NextVex(Graph G,int i,int j){
if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum){ //i,j合理 
for(int k=j+1;k<G.vexnum;k++) 
if(G.arcs[i][k]!=INFINITY) return k; 
} 
return -1; 
} 

void print(Graph G)//输出图的邻接矩阵(列为弧尾,行为弧头)
{
    int i,j,count=0,temp[MAX_VEX];
    printf("图的邻接矩阵为:\n");
    printf("        ");
    for(i=0;i<MAX_VEX;i++)
    {
        if(G.vexs[i]!=NULL)
        {
            printf("%c  ",G.vexs[i]);
            temp[count]=i;
            count++;
        }
    }
    printf("\n");
    for(i=0;i<count;i++)
    {
        printf("       ");
        printf("%c",G.vexs[temp[i]]);
        for(j=0;j<count;j++)
            printf("%d  ",G.arcs[temp[i]][temp[j]]);
        printf("\n");
    }
    
}

//深度优先遍历 
void DFS(Graph G,int k){ 
int i; 
if(k==-1){ //第一次执行DFS时,k为-1 
for(i=0;i<G.vexnum;i++) 
if(!visited[i]) DFS(G,i); //对尚未访问的顶点调用DFS 
} 
else{ 
visited[k]=true;
if(z==1)
printf("%c",G.vexs[k]);
else printf(" -> %c",G.vexs[k]); ++z;//访问第k个顶点 
if((z-1)%G.vexnum==0) z=1;
for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i)) 
if(!visited[i]) DFS(G,i); //对k的尚未访问的邻接顶点i递归调用DFS 
} 
}
//广度优先遍历 
void BFS(Graph G){ 
int k; 
Queue Q; //辅助队列Q 
Q.InitQueue(); 
for(int i=0;i<G.vexnum;i++) 
if(!visited[i]){ //i尚未访问 
visited[i]=true;
 printf("%c ",G.vexs[i]); 
Q.EnQueue(i); //i入列 
while(Q.front!=Q.rear){ 
Q.DeQueue(k); //队头元素出列并置为k 
for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w)) 
if(!visited[w]){ //w为k的尚未访问的邻接顶点 
visited[w]=true; 
printf("-> %c ",G.vexs[w]); 
Q.EnQueue(w); 
} 
} 
} printf("\n  请继续选择:\n");
} 


void choose(Graph G){//对输入选项调用相应的函数执行操作
int i,m; 
visited=(bool *)malloc(G.vexnum*sizeof(bool));
scanf("%d",&m);
switch(m){
case 1:
for(i=0;i<G.vexnum;i++) 
visited[i]=false;
print(G);break;
case 2: 
printf("广度优先遍历: "); 
for(i=0;i<G.vexnum;i++) 
visited[i]=false; 
BFS(G); choose(G); printf("\n");break;
case 3:
printf("深度优先遍历: "); 
for(i=0;i<G.vexnum;i++) 
visited[i]=false; 
DFS(G,-1);  
printf("\n  请继续选择:\n");choose(G);break;
case 4:printf("程序结束."); break;
default : printf("    输入错误!\n请在1-4中选择:\n"); choose(G);
}
}
//主函数 
void main(){ 
int i,m; 
Graph G; 
CreateUDN(G); 
printf("有如下选项供选择：\n");
printf("***********************************************************************\n");
printf("|*| 1:输出邻接矩阵图  2:广度优先遍历  3:深度优先遍历  4:退出本程序！|*|\n");
printf("***********************************************************************\n");
printf("请选择(1--4):\n");
choose(G);
}