校園導航系統

【問題描述】

當對校園參觀時，會遇到這樣的問題：如果從校園的某個位置出發，參觀到校園中的所有景點，怎樣設計路線，使參觀者既能參觀所有景點又使走的路程最少。

【資料描述】

定義一個鄰接矩陣存儲結構，用來存儲點和邊的資訊。

定義一個輔助數組closedge,該數組包含兩個分量，lowcost記錄從U到V-U具有最小代價的邊，adjvex記錄改邊依附于U中的頂點。

typedef char ElemType;

typedef struct {

ElemType vexs[max];
int arcs[max][max];
int vexnum,arcnum;           

}MGraph;

struct {

ElemType adjvex;
int lowcost;           

}closedge[max];

【算法思想】

(1)已知校園中各景點和路徑的權重，使參觀者既能參觀所有景點又使走的路程最少。即求最小生成樹，使得路徑保持連通且經過所有邊權值之和最小。

(2)用到Prim算法求最小生成樹，算法思想大體為：

設N=(V,E)是一個連通網，T=(U,TE)是N的最小生成樹，TE是N中最小生成樹中邊的集合。

①初始化：令U={u0|u0∈V},TE={}。其中u0是頂點集合V中的某個頂點。

②選擇：在所有u∈U,v∈V-U的邊(u,v)∈E中，選擇一條代價最小的邊(ui,vj),将(ui,vj)并入集合TE,同時vj并入U。

③反複執行步驟②，直至U=V為止。

TE必有n-1條邊，則T為N的最小生成樹。

【C源程式】

#include<stdio.h>
#include<stdlib.h>
#include<time.h> 
#define max 20
#define INFINITY 1000
typedef char ElemType;
typedef struct {
    ElemType vexs[max];
    int arcs[max][max];
    int vexnum,arcnum;
}MGraph; 
struct {
    ElemType adjvex;
    int lowcost;
}closedge[max];

//傳回頂點下标 
int LocateVex(MGraph G,ElemType v)
{
    for(int i=0;i<G.vexnum;i++)
    {
        if(v==G.vexs[i])
            return i;
    }
    return -1;
}
//建立無向圖鄰接矩陣 
void CreatGraph(MGraph &G)
{
    int  i, j, k,m,n;
       char v1, v2;
       srand(time(0));
   printf("輸入校園中景點數及弧數：\n");
   scanf( "%d%d", &G.vexnum, &G.arcnum );
   getchar(); 
   printf("輸入校園中所有景點：\n" );
   for( i=0; i<G.vexnum; i++ )
   {   
           G.vexs[i]=getchar(); 
           getchar();   }
   for( i=0; i<G.vexnum; i++ )          //初始化鄰接矩陣
      for( j=0; j<G.vexnum; j++ )
          G.arcs[i][j]=INFINITY;
   for( k=0; k<G.arcnum; k++ )
   {
           int w;
           printf("輸入校園中的兩個景點确定邊：\n" );
       v1=getchar(); getchar();
       v2=getchar(); getchar();
       m= LocateVex(G,v1);  n= LocateVex(G,v2);
       printf("請輸入邊的權重：\n"); 
       scanf("%d",&w);
       getchar();
       G.arcs[m][n]=w;G.arcs[n][m]=w;
   }
   printf("鄰接矩陣為：\n"); 
   for( i=0; i<G.vexnum; i++ ) 
   {      
      for( j=0; j<G.vexnum; j++ )
          printf("%d\t",G.arcs[i][j]);
    printf("\n"); 
}
}
//Prim(适用于邊稠密的網) 
int MiniSpanTree_Prim(MGraph G,ElemType u)
{
    int k=LocateVex(G,u);
    for(int j=0;j<G.vexnum;j++)
    {
            if(j!=k)
            {
                closedge[j].adjvex=u;
                closedge[j].lowcost=G.arcs[k][j];
            }
    }
    closedge[k].lowcost=0;
    int minsum=0;
    for(int i=1;i<G.vexnum;i++)
    {
        int minCost=INFINITY;
        for(int j=0;j<G.vexnum;j++)//找最小值 
        {
            if(closedge[j].lowcost!=0&&closedge[j].lowcost<minCost){
                minCost = closedge[j].lowcost;
                k=j;
            }
        }
        printf("%c----%c %d\n",closedge[k].adjvex,G.vexs[k],closedge[k].lowcost);
        minsum+=closedge[k].lowcost;
        closedge[k].lowcost=0;
        for(int j=0;j<G.vexnum;j++)
        {
            if(closedge[j].lowcost!=0&&G.arcs[k][j]<closedge[j].lowcost)
            {
                closedge[j].adjvex = G.vexs[k];
                closedge[j].lowcost = G.arcs[k][j];
            }
        }
    }
    return minsum;
}
int main()
{
     MGraph G;
    CreatGraph(G);                                                           //建立無向圖的鄰接矩陣 
    printf("請輸入從哪個景點出發：\n");
    char u;
    scanf("%c",&u);
    printf("\n 最短路徑權重之和為；%d.\n", MiniSpanTree_Prim(G,u));//輸出路徑與權值
    return 0;
 }            

【小結】

校園導航問題：

不足之處：将問題過于簡單化，就簡單實作建立賦權圖的鄰接矩陣存儲結構，和用Prim算法求最短生成樹，跟校園導航沒有太多關系，不實用。

通過進行資料結構課程設計，對資料結構和算法有了進一步深刻的認識。也發現了自己很多問題。對許多重要的算法不能熟練的運用。仍需對代碼進一步完善。

【參考文獻】

[1] 趙永升，宋麗華，資料結構．北京：電子工業出版社，2019.
[2] 嚴蔚敏，資料結構（C語言版）．北京：清華大學出版社，2007.