#include<stdio.h>
#include<stdlib.h>

#define LEN  sizeof(struct C)

struct C{
           int k;
           struct C*next;
         };

int *a;//存放定点数据
int *visit;//定点访问标记
int s=0;  
int**b;//存放邻接矩阵



//深度优先便历
void DFS(int i)
{ 
  int j;
  visit[i]=1;
  printf("%d->",a[i]);
  for(j=0;j<s;j++)
   if(b[i][j]==1&&!visit[j])
     DFS(j);

}//DFS

void depthfirst()
{
    int i;
    for(i=0;i<s;i++)
    if(!visit[i]) DFS(i);
    
}

//无向图的存储（邻接矩阵）

void creatgraphics(int n,int arcnum )
{
  int i=0,j=0,k=0;
  s=n;
  a=(int *)malloc(n*sizeof(int));



 b=(int**)malloc(sizeof(int*)*n);
 for (i=0;i<n;i++) 
 {
    b[i] = (int*)malloc(sizeof(int)*n);
 }


  visit=(int *)malloc(n*sizeof(int));
    

  for(i=0;i<n;i++)//构造顶点向量
  { 
    printf("请输入顶点信息\n");
    scanf("%d",&a[i]);
  }


for(i=0;i<n;i++)
    visit[i]=0;
  
for(i=0;i<n;i++)//初始化邻接矩阵
  for(j=0;j<n;j++)
     b[i][j]=0;

//构造邻接矩阵
   for(k=0;k<arcnum;k++)
   {
    printf("请输入有边邻接的两个顶点\n");
    scanf("%d %d",&i,&j);
        if( b[i-1][j-1]!=1)
        {
           b[i-1][j-1]=1;
           b[j-1][i-1]=b[i-1][j-1];
        }
   }
 
}//creatgraphics


//广度优先遍历
void breadfirst(int vexnum)//vexnum顶点数
{
    int i,j,x=0;
    //建队列
    struct C *duitou,*duiwei,*A; 
    A=duitou=duiwei=(struct C*)malloc(LEN);
    duitou->next=NULL; 
    duitou->k=a[0];
    for(i=0;i<s;i++)
       visit[i]=0;
    for(i=0;i<vexnum;i++)
    {
       if(!visit[i])
       {
          while(duitou!=NULL)
          { 
             //打印队头
              printf("%d->",duitou->k);
              for(i=0;i<s;i++)
                    if(a[i]==duitou->k) 
                    {
                        x=i;
                        visit[i]=1;
                    }
                      
               for(j=0;j<s;j++)
               {
                   if(b[x][j]=1&&!visit[j])
                   {
                       //a[j]入队
                    duiwei=(struct C*)malloc(LEN);
                    A->next=duiwei;
                    duiwei->k=a[j];
                    duiwei->next=NULL;
                    A=duiwei;
                   }
               }

               //出队
              duitou=duitou->next;
          }//while
        

       }//if

    }//for
  printf("\n");
}//breadfirst

main()
{
    int y,v,z;

loop1:
    printf("请选择遍历方式\n1:深度优先(按 1)\n2:广度优先(按 2)\n3:深度优先+广度优先()(按 3)\n");
    scanf("%d",&z);

    if(z==1)
    {
        printf("请输入图中顶点个数\n");
        scanf("%d",&y);

        printf("请输入图中边的条数\n");
        scanf("%d",&v);
         
        creatgraphics(y,v);
        printf("深度优先遍历结果:\n");
        depthfirst();

    }
    if(z==2)
    {
        printf("请输入图中顶点个数\n");
         scanf("%d",&y);

        printf("请输入图中边的条数\n");
        scanf("%d",&v);
       
        creatgraphics(y,v);
        printf("广度优先遍历结果:\n");
        breadfirst(y);
    }
   if(z==3)
    {
        printf("请输入图中顶点个数\n");
         scanf("%d",&y);

        printf("请输入图中边的条数\n");
        scanf("%d",&v);
       
        creatgraphics(y,v);
        printf("深度优先遍历结果:\n");
        depthfirst();
        printf("\n");
        printf("广度优先遍历结果:\n");
        breadfirst(y);
    }
   if(z!=1&&z!=2&&z!=3)
   {
       printf("wrong command!\n");
       goto loop1;
   }
}