#include<stdio.h>
#include <stdlib.h>
#define vertexnum 100       //定義最大可輸入的結(jié)點(diǎn)個(gè)數(shù)
#define QueueMax  100
typedef struct  node        //定義圖形的頂點(diǎn)結(jié)構(gòu)
{
   int  vertex;             //圖中的頂點(diǎn)信息為數(shù)字
   struct  node  *next;
}Graph;
Graph head[vertexnum];      //鄰接表的表頭結(jié)點(diǎn)
int Visited[vertexnum];     //遍歷記錄
int Front=-1;
int Rear=-1;
int Queue[QueueMax];

int Enqueue(int Vertex)       //元素入隊(duì)
{
    if (Rear>=QueueMax)       //隊(duì)列已滿
        return -1;
    else
    {
        Rear  ;               //隊(duì)列尾端指針后移
        Queue[Rear]=Vertex;   //將值存入隊(duì)列中
        return 1;
    }
}

int Dequeue()                //元素出隊(duì)
{
    if (Front>=Rear)          //隊(duì)列已空
        return -1;
    else
    {
        Front  ;              //隊(duì)頭指針后移
        return Queue[Front];
    }
}

void BFS(int Vertex)//廣度優(yōu)先搜索
{
int i;
Graph  *searchP;
searchP=&(head[Vertex]);
    printf("%d  ",searchP->vertex);
Visited[Vertex]=1;
Enqueue(searchP->vertex);
 while(i!=-1)
    {

   i=Dequeue();
   searchP=&(head[i]);
    while(searchP!=NULL)
{
           if(Visited[searchP->vertex]!=1)
   {
   if(searchP->vertex==0) ;
   else printf("%d   ",searchP->vertex);
             Visited[searchP->vertex]=1;
             Enqueue(searchP->vertex);
   }
           searchP=searchP->next;
}
     }
}

void Create_l_Graph(int Vertex1,int Vertex2,int no)
{                      //以鄰接鏈表建立圖形
  Graph  *searchP;     //結(jié)點(diǎn)聲明
  Graph  *New;         //新結(jié)點(diǎn)聲明
  New=(Graph *)malloc(sizeof(struct node));
  if (New!= NULL )
  {
    New->vertex=Vertex2;
    New->next=NULL;
    searchP=&(head[Vertex1]);
    while(searchP->next!=NULL)
       searchP=searchP->next;
    searchP->next =New;
if(no==0)
{
New=(Graph *)malloc(sizeof(struct node));
New->vertex=Vertex1;
        New->next=NULL;
        searchP=&(head[Vertex2]);
        while(searchP->next!=NULL)
           searchP=searchP->next;
        searchP->next =New;
    }
  }
}

void showmenu()
{                   //顯示菜單
printf("    歡迎使用圖的操作演示軟件\n");
printf("\t1、創(chuàng)建圖的鄰接表\n");
printf("\t2、圖的輸出\n");
printf("\t3、圖的廣度優(yōu)先遍歷\n");
printf("\t4、退出程序\n");
}

void print_l_graph(Graph *head)
{                     //輸出鄰接鏈表的數(shù)據(jù)
    Graph  *searchP;
    searchP=head->next;
    while(searchP!=NULL)
    {
      printf("[%d]",searchP->vertex);
      searchP=searchP->next;
     }
    printf("\n");

}

void main()
{
   int source;           //圖中一條邊的起始頂點(diǎn)
   int destination;      //圖中一條邊的終止頂點(diǎn)
   int i,j;
   int vermax;           //定義圖中最大的頂點(diǎn)數(shù)
   int edgemax;          //定義圖中最大的邊數(shù)
   int choice;
   int no;

   while(1)
{
showmenu();
printf("   請輸入你的選擇：");
scanf("%d",&choice);
fflush(stdin);//清除鍵盤緩沖區(qū)
switch(choice)
{
          case 1:printf("請輸入圖的類別（有向圖-1，無向圖-0）:");
     scanf("%d",&no);
     printf("請輸入圖中的總頂點(diǎn)數(shù)和邊數(shù):");
                 scanf("%d%d",&vermax,&edgemax);
     for(i=1;i<vermax;i  )
{
head[i].vertex = i;
head[i].next = NULL;
}
for(i=1;i<=edgemax;i  )
{
printf("請輸入第%d條邊的起點(diǎn)：",i);
scanf("%d",&source);
printf("請輸入第%d條邊的終點(diǎn)：",i);
scanf("%d",&destination);
if(source==destination)   
   printf("輸入有誤！\n");//出錯(cuò)：自身循環(huán)
        else                 //調(diào)用建立鄰接鏈表
                        Create_l_Graph(source,destination,no);
}
     printf("圖創(chuàng)建成功，按任意鍵繼續(xù)…\n");
 getch();
 system("cls");
 break;
  case 2:printf("圖的鄰接表如下：\n"); 
 for(i=1;i<=vermax;i  )
{
printf("頂點(diǎn)[%d]:",i);
print_l_graph(&head[i]);//調(diào)用輸出鄰接鏈表數(shù)據(jù)
}
 printf("\n");
 system("pause");
 system("cls");
 break;
  case 3:for(i=1;i<=vermax;i  )
                     Visited[i]=0;
     printf("請輸入遍歷的起點(diǎn):");
 scanf("%d",&source);
     printf("圖的廣度優(yōu)先遍歷結(jié)果為：\n");
     BFS(source);
 printf("END\n");
 system("pause");
 system("cls");
 break;
  case 4:return;
  default:
     printf("你的輸入有誤，請從新輸入！\n");
 system("pause");
 system("cls");
}
}   
}