#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。創(chuàng)建圖**********************/  
    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("圖已經創(chuàng)建完畢！");  
    }  
      
    /***********************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個點出發(fā)深度優(yōu)先周游圖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)  
    //深度優(yōu)先周游圖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)  
    //將順序循環(huán)隊列sq置空（初始化）  
    {  
       sq->front=0;  
       sq->rear=0;  
    }  
    /*****************************************************************************/  
    int QueueIsEmpty(SEQQUEUE sq)  
    //如果順序循環(huán)隊列sq為空，成功返回1，否則返回0  
    {  
       if (sq.rear==sq.front)   
          return(1);  
       else  
          return(0);  
    }   
    /*****************************************************************************/  
    int QueueFront(SEQQUEUE sq,DATATYPE *e)  
    //將順序循環(huán)隊列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出發(fā)廣度優(yōu)先周游圖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)  
    //深度優(yōu)先周游圖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);  
    }  

標簽：

版權申明：本站文章部分自網絡，如有侵權，請聯系：west999com@outlook.com
特別注意：本站所有轉載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權歸原作者所有，如需使用，請與原作者聯系。