#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#include"dos.h"
#define M 60

/*定义链表中的结点类型*/
typedef struct node
{
 int vex; /* 顶点域 */
 struct node *link; /* 指针域*/
}JD;

/*定义表头结点*/
typedef struct tnode
{
 int data; /*数据域*/
 //char data;
 struct node *link; /*指针域指向链表中第一个结点*/
}TD;

/*建立无向图的邻接表*/
void creatljb(TD ad[], int n)
{
 JD *p;
 int i,j,k;
 for(k=1;k<=n;k++)

 ad[k].link=NULL; /*初始化表结点为空*/
 printf("please input the node that are conected with the known node\n");
 printf("(Input 0,0 to finish the enter work)");
 scanf("%d,%d",&i,&j); /*输入一条边相关联的两个表结点*/
 while((i>0)&&(j>0)) /*结束时以（0，0）表示*/
 {
   p=(JD *)malloc(sizeof(JD)); /*开辟新单元生成新结点*/
   p->vex=j;
   p->link=ad[i].link;
   ad[i].link=p; /*结点j插入到第i个链表*/
   p=(JD *)malloc(sizeof(JD));
   p->vex=i;
   p->link=ad[j].link;
   ad[j].link=p; /*结点i插入到第j个链表*/
   printf("please input the node that are conected with the node\n");
   scanf("%d,%d",&i,&j); /*继续输入两个邻接顶点*/
 }
}

/*广度优先遍历函数生成*/
void bfs(TD g[], int v, int c[])
{
 int q[M],r=0,f=0; /*f指向队首r指向队尾*/
 JD *p;
 c[v]=1;
 printf("the visited node is %d\n",v);
 q[0]=v;
 while(f<=r) /*队列不空*/
 {
   v=q[f++]; /*访问过的顶点出队*/
   p=g[v].link; /*p指向v的第一个邻接点*/
   while(p!=NULL)
   {
     v=p->vex;
     if(c[v]==0)
     {
       c[v]=1;
       printf("%d\n",v);
       q[++r]=v; /*访问该顶点并近队*/
     }
     p=p->link; /*取下一个邻接点*/
   }
 }
}

/*深度优先递归函数*/
void dfs(TD g[], int v, int c[])
{
 JD *p;
 int i;
 c[v]=1;
 printf(" the dfs node is %d\n",v); /* 访问顶点v*/
 for(p=g[v].link;p!=NULL;p=p->link) /*p最初指向V的第一个相邻顶点*/
 {
   i=p->vex; /*得出p指针所指邻接点的序号*/
   if(c[i]==0)
   dfs(g,i,c); /*递归调用*/
 }
}

/*遍历图*/
void blt(TD g[], int n)
{
 int v;
 int c[M];
 for(v=1;v<=n;v++)
   c[v]=0;/*访问标识数组初始化*/
 for(v=1;v<=n;v++)
   if(c[v]==0)
     dfs(g,v,c); /*调用dfs函数*/
}

/*主函数*/
void main(void)
{
 clrscr();
 int n,x,v,y;
 int c[10];
 TD a[10];
 printf("please input n : ");
 scanf("%d",&n);
 creatljb(a,n);
 first:
   printf("Please input the node v you want to start with : "); /*起始点*/
   scanf("%d",&v);
   if(v>10)
   {
     printf("ERROR!! WRONG INPUT NUMBER\n");
     goto first;
   }
   else
   {
   /* printf("please input y : ");
     scanf("%d",&y); */
     printf("please input what you want to do (x=1,2,3) :\n ");
     printf("(1:bfs; 2:dfs; 3:break;)"); /*选择遍历类型*/
     scanf("%d",&x);
     switch(x){
       case 1 : bfs(a,v,c);
       case 2 : dfs(a,v,c);
                blt(a,n);
       case 3 : printf("ESC");
     }
   }
   printf(" Go through the Graph: finished!");
   getch(); /*得一字符结束*/
 }