經典算法8：檢索與周游之廣度和深度優先遍歷圖

    #include <stdio.h>

    typedef  int  datatype;   /假定線性表元素的類型為整型/


#define  maxsize  1024    /*假定線性表的最大長度為1024*/  
# define n 100            /* 圖的頂點最大個數 */  
typedef char VEXTYPE;  /* 頂點的數據類型 */  
typedef float ADJTYPE;  /* 權值類型 */  
typedef struct  
{   
    VEXTYPE vexs[n] ;  /* 頂點信息數組 */  
    ADJTYPE arcs[n][n] ; /* 邊權數組 */  
    int num ;    /* 頂點的實際個數 */  
}GRAPH;  

/***********************1。置空圖**********************/  
void GraphInit(GRAPH  *L)  
{  
 L->num=0;  
}  

/***********************2。求結點數**********************/  
int GraphVexs(GRAPH  *L)  
{  
 return(L->num);  
}  

/***********************3。創建圖**********************/  
void GraphCreate(GRAPH  *L)  
{  
 int i,j;  
 GraphInit(L);  
 printf("請輸入頂點數目：");  
 scanf("%d",&L->num);  
 printf("請輸入各頂點的信息(單個符號）：");  
 for(i=0;i<L->num;i++)  
 {  
  fflush(stdin);  
  scanf("%c",&L->vexs[i]);  
 }  
 printf("請輸入邊權矩陣的信息：");  
 for(i=0;i<L->num;i++)  
 {  
  for(j=0;j<L->num;j++)  
  {  
   scanf("%f",&L->arcs[i][j]);  
  }  
 }  
 printf("圖已經創建完畢！");  
}  

/***********************4。圖的輸出**********************/  
void GraphOut(GRAPH  L)  
{  
     int i,j;  
     printf("\n圖的頂點數目為：%d",L.num);  
     printf("\n圖的各頂點的信息為：\n");  
     for(i=0;i<L.num;i++)  
        printf("%c  ",L.vexs[i]);  
     printf("\n圖的邊權矩陣的信息為：\n");  
     for(i=0;i<L.num;i++)  
     {  
          for(j=0;j<L.num;j++)  
          {  
             printf("%6.2f ",L.arcs[i][j]);  
          }  
          printf("\n");  
     }  
     printf("圖已經輸出完畢！");  
}  

/***********************5。圖的深度周游**********************/  
void DFS(GRAPH  g,int qidian,int mark[])  
//從第qidian個點出發深度優先周游圖g中能訪問的各個頂點  
{  
     int v1;  
     mark[qidian]=1;  
     printf("%c   ",g.vexs[qidian]);  
     for(v1=0;v1<g.num;v1++)  
     {  
         if(g.arcs[qidian][v1]!=0&&mark[v1]==0)  
            DFS(g,v1,mark);  
     }  
}  
/***********************6。圖的深度周游**********************/  
void GraphDFS(GRAPH  g)  
//深度優先周游圖g中能訪問的各個頂點  
{  
 int qidian,v,v1,mark[maxsize];  
 printf("\n深度周游：");  
 printf("\n請輸入起點的下標：");  
 scanf("%d",&qidian);  
 for(v=0;v<g.num;v++)  
 {  
  mark[v]=0;  
 }  
 for(v=qidian;v<g.num+qidian;v++)  
 {  
  v1=v%g.num;  
  if(mark[v1]==0)  
   DFS(g,v1,mark);  
 }  
}  
typedef  int DATATYPE;     //隊列元素的數據類型  
typedef  struct  
{    
 DATATYPE data[maxsize]; //隊中元素  
   int front,rear;   //隊頭元素下標、隊尾元素后面位置的下標  
} SEQQUEUE;  
/*****************************************************************************/  
void QueueInit(SEQQUEUE *sq)  
//將順序循環隊列sq置空（初始化）  
{  
   sq->front=0;  
   sq->rear=0;  
}  
/*****************************************************************************/  
int QueueIsEmpty(SEQQUEUE sq)  
//如果順序循環隊列sq為空，成功返回1，否則返回0  
{  
   if (sq.rear==sq.front)   
      return(1);  
   else  
      return(0);  
}   
/*****************************************************************************/  
int QueueFront(SEQQUEUE sq,DATATYPE *e)  
//將順序循環隊列sq的隊頭元素保存到e所指地址，成功返回1，失敗返回0  
{  
 if (QueueIsEmpty(sq))   
    { printf("queue is empty!\n");return 0;}  
    else  
    { *e=sq.data[(sq.front)]; return 1;}  
}  
/*****************************************************************************/  
int QueueIn (SEQQUEUE *sq,DATATYPE x)  
//將元素x入隊列sq的隊尾，成功返回1，失敗返回0  
{   
 if (sq->front==(sq->rear+1)%maxsize)  
 {    
  printf("queue is full!\n");  
  return 0;  
 }  
 else  
 {     
  sq->data[sq->rear]=x;  
  sq->rear=(sq->rear+1)%maxsize;  
  return(1);  
 }  
}  
/*****************************************************************************/  
int QueueOut(SEQQUEUE *sq)  
//將隊列sq隊首元素出隊列，成功返回1,失敗返回0  
{  
    if (QueueIsEmpty(*sq))  
    {    
  printf("queue is empty!\n");  
  return 0;  
 }  
    else  
    {          
  sq->front=(sq->front+1)%maxsize;  
  return  1;  
    }  
}  
/***********************7。圖的廣度周游**********************/  
void BFS(GRAPH g,int v,int mark[])  
//從v出發廣度優先周游圖g中能訪問的各個頂點  
{   
     int v1,v2;  
     SEQQUEUE q;  
     QueueInit(&q);   
     QueueIn(&q,v);  
     mark[v]=1;  
     printf("%c   ",g.vexs[v]);  
     while(QueueIsEmpty(q)==0)    
     {   
          QueueFront(q,&v1);  
          QueueOut(&q);   
          for(v2=0;v2<g.num;v2++)  
          {  
               if(g.arcs[v1][v2]!=0&&mark[v2]==0)  
               {   
                    QueueIn(&q,v2);  
                    mark[v2]=1;  
                    printf("%c   ",g.vexs[v2]);  
               }  
              }  
     }  
}  
/***********************8。圖的廣度周游**********************/  
void GraphBFS(GRAPH  g)  
//深度優先周游圖g中能訪問的各個頂點  
{  
 int qidian,v,v1,mark[maxsize];  
 printf("\n廣度周游：");  
 printf("\n請輸入起點的下標：");  
 scanf("%d",&qidian);  
 for(v=0;v<g.num;v++)  
 {  
  mark[v]=0;  
 }  
 for(v=qidian;v<g.num+qidian;v++)  
 {  
  v1=v%g.num;  
  if(mark[v1]==0)  
   BFS(g,v1,mark);  
 }  
}  

/***********************主函數**********************/  

void main()  
{  
 GRAPH tu;  
 GraphCreate(&tu);  
 GraphOut(tu);  
 GraphDFS(tu);  
 GraphBFS(tu);  
}  </pre>