#define MAX_V 20
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include "tu2.h"

typedef struct{
  int Vertex[MAX_V];//頂點
  int R[MAX_V][MAX_V];//鄰接矩陣數組
  int vexnum;//頂點號
}Graph;


void creatgraph(Graph *g,int n)
{
  int i,j,start,end;
  g->vexnum=n;
  
  for(i=1;i<=n;i++)
  {
    g->Vertex[i]=i;
  }
  
  for(i=1;i<=n;i++)/*初始化R*/
   for(j=1;j<=n;j++)
    {
      g->R[i][j]=0;
    }
  
  printf("請輸入關系圖列如1，2 2，3 并且用0，0結束:\n");
  scanf("%d,%d",&start,&end);
  while(start!=0&&end!=0)
   {
    g->R[start][end]=1;
    g->R[start][end]=1;
    scanf("%d,%d",&start,&end);
   }
}


void printgraph(Graph *g)/*打印圖的鄰接矩陣*/
{
int i,j;
for(i=1;i<=g->vexnum;i++)
{ for(j=1;j<=g->vexnum;j++)
   {
     printf("%2d ",g->R[i][j]);
   }
   printf("\n");
   }
}

int visited[MAX_V];

void visitvex(Graph *g,int vex)/*訪問頂點*/
{
printf("%d ",g->Vertex[vex]);
}


int firstadjvex(Graph *g,int vex)/*獲取第一個未被訪問的鄰接節點*/
{
int w,i;
for(i=1;i<=g->vexnum;i++)
  {
   if(g->R[vex][i]==1&&visited[i]==0)
    {
      w=i;
      break;
    }
   else
    {
      w=0;
    }
  }
  return w;
}

int nextadjvex(Graph *g,int vex,int w)/*獲取下一個未被訪問的鄰接節點(深度遍歷)*/
{
  int t;
  t=firstadjvex(g,w);
  return t;
}

  void dfs(Graph *g,int vex)
   {
    int w;
    visited[vex]=1;
    visitvex(g,vex);
    for(w=firstadjvex(g,vex);w>0;w=nextadjvex(g,vex,w))
      if(!visited[w])
       {
dfs(g,w);
       }
   }

   void dfstraverse(Graph *g)
   {
     int i;
     for(i=1;i<=g->vexnum;i++)
       visited[i]=0;
     for(i=1;i<=g->vexnum;i++)
       if(!visited[i])
  {dfs(g,i);}
   }


void BESTraverse(Graph *g)
{
  int i;
  Queue *q=(Queue *)malloc(sizeof(Queue));
  for(i=1;i<=g->vexnum;i++)
  {
   visited[i]=0;
  }
  initqueue(q);
  for(i=1;i<=g->vexnum;i++)
  {
    if(!visited[i])
     {
       visited[i]=1;
       visitvex(g,g->Vertex[i]);
       enqueue(q,g->Vertex[i]);
       while(!quempty(q))
 {
   int u,w;
   u=dequeue(q);
   for(w=firstadjvex(g,u);w>0;w=nextadjvex(g,u,w))
     {
       if(!visited[w])
        {
   visited[w]=1;
   visitvex(g,w);
   enqueue(q,w);
        }
     }
 }
     }
  }
}