C++實現景區旅遊資訊管理系統

//深度優先搜尋導遊線路
int visited[M]={0};
int np=0;//找到的景點個數
int p[M];//表示各個景點的入度值
void DFS(int c){
    //c為景點編號
    np++;//每遞迴呼叫一次就自加一次，作為判斷是否到了最後一個景點
    p[c]++;
    if(np==S.count){
        //到了最後一個景點
        cout<<S.mat.Pname[c]<<endl;
        returnMainFace();
    }else{
       cout<<S.mat.Pname[c]<<"-->";
    }
     visited[c]=1;
     for(int i=0;i<S.count;i++){
        if(S.mat.m[c][i]>0&&visited[i]==0){
             DFS(i);
             if(S.count>np){
                 cout<<S.mat.Pname[c]<<"-->";
                 p[c]++;
             }
         }
     }
     if(np==S.count)
         returnMainFace();
}
void guide_line()//導遊線路
{
     checked();
     cout<<"n*請輸入起始景點的景點編號：";
     int c;
     cin>>c;
     c--;
     for(int i=0;i<S.count;i++){
         visited[i]=0;
         p[i]=0;//入度置初值為0
     }
     np=0;
     cout<<"*形成的導遊線路圖（採取深度優先策略）如下所示：nnt";
     DFS(c);
}
//Floyd（佛洛依德）演演算法，A[M][M]表示最短距離，path[M][M]表示輔助陣列，記住前驅
void Floyd(int A[M][M],int path[M][M]){
     int i,j,k;
     for(i=0;i<S.count;i++){
         for(j=0;j<S.count;j++){
            if(S.mat.m[i][j]==0&&i!=j){
                 //如果兩點之間沒有邊相連，則權為無窮大
                 A[i][j]=INF;//INF=999666333
             }else if(i==j){
                 A[i][j]=0;
             }else{
                 //S.mat.m[i][j]表示兩個景點之間的道路長度
                A[i][j]=S.mat.m[i][j];
             }
             //給所有的path[i][j]賦值
             if(i!=j&&S.mat.m[i][j]<INF){
                 path[i][j]=i;
             }else{
                 //（i==j&&S.mat.m[i][j]=INF
                 path[i][j]=-1;
             }
         }
     }
        //k注意放到最外層，讓A[i][j]檢測都經過每一個k
         for(k=0;k<S.count;k++){
             for(i=0;i<S.count;i++){
                for(j=0;j<S.count;j++){
                    if(A[i][j]>A[i][k]+A[k][j]){//如果i->j的權值大於i->k->j的權值
                        A[i][j]=A[i][k]+A[k][j];
                        path[i][j]=path[k][j];//path[k][j]=k前驅?k是指向的下一個景點
                     }
                 }
             }
         }
}
void min_distance()//最短路徑、距離
{
     checked();
     int A[M][M],path[M][M];
     Floyd(A,path);//A是一個景點到另一個景點的最短路徑的長度
     while(true){
         Num_Name();//編號對應的景點名稱
         int i,j,k,s;
         int apath[M],d;//apath[M]是記錄路徑的陣列
         bool flag=true;
         while(flag){
             cout<<"t-景點1：";
             cin>>i;
             i--;
            if(i<0||i>S.count-1){
                 cout<<"*請輸入合法的景點編號:n";
             }else{
                 flag=false;
             }
         }
         flag=true;
         while(flag){
             cout<<"t-景點2：";
             cin>>j;
             j--;
            if(j<0||j>S.count-1){
                 cout<<"*請輸入合法的景點編號:n";
             }else{
                 flag=false;
             }
         }
        if(A[i][j]<INF&&i!=j){
             k=path[i][j];//k是指向的下一個景點
             d=0;//路徑有d+2個景點,是陣列apath的下標
             //將待輸出的路徑的點存放在棧apath中
             apath[d]=j;//最後一個景點
            while(k!=-1&&k!=i){
                 d++;
                 apath[d]=k;
                 //再繼續判斷還有沒有景點
                 k=path[i][k];
             }
             d++;
             apath[d]=i;//加上第一點
             cout<<"n*從 "<<S.mat.Pname[i]<<" 到"<<S.mat.Pname[j]<<" 最短路徑為：";
             cout<<S.mat.Pname[apath[d]];//apath[M]陣列最後一個，就是第一個起點,相當於棧
             for(s=d-1;s>=0;s--){//將剩下的景點（apath[M]陣列剩下的元素）列印出來
                 cout<<"-->"<<S.mat.Pname[apath[s]];
             }
             cout<<" ，最短距離為："<<A[i][j]<<endl;//Floyd演演算法已經將最短路徑算出來存放到了A[i][j](將INF的值用最短路徑代替了)
         }else if(i==j){
             cout<<"n*景點輸入不合法，輸入的兩個景點不能相同!n";
         }else{
             cout<<"n*這兩個景點間不存在路徑n";
         }
         cout<<"n是否繼續執行最短路徑和最短距離的查詢（Y/N）";
         Y_N();
     }
     returnMainFace();
}
//道路修建規劃圖、最小生成樹(prime演演算法)
void build_road()
{
     checked();
     cout<<"n*道路修建規劃圖（prime演演算法）規劃如下：n";
     //Ai[M]表示待選邊的權值,鄰接矩陣的一行,closest[M]：點編號陣列，記錄下一條路的起點景點的編號
     intAi[M],min,closest[M],i,j,k,sum=0,num=0;//num表示第幾條路
     int A[M][M];
     //賦權值
     for(i=0;i<S.count;i++){
         for(j=0;j<S.count;j++){
            if(S.mat.m[i][j]==0&&i!=j){
                 A[i][j]=INF;
             }else if(i==j){
                 A[i][j]=0;
             }else{
                A[i][j]=S.mat.m[i][j];
             }
         }
     }
     for(i=0;i<S.count;i++){
         Ai[i]=A[0][i];//取第一行存四個Ai[i]，就是一個景點到所有景點的權值
         closest[i]=0;//0
     }
     for(i=1;i<S.count;i++){
         min=INF;
         //從Ai[j]中選出最小的值存放在min
         for(j=0;j<S.count;j++){
            if(Ai[j]!=0&&Ai[j]<min){
                 min=Ai[j];
                 k=j;//記錄最小的值的列j:k=j，為了下面標誌此路已選
             }
         }
         if(min<INF){
             cout<<"t-第 "<<++num<<" 條路： 從"<<S.mat.Pname[closest[k]]<<" 到"<<S.mat.Pname[k]<<" , 該道路長度為："<<min<<endl;
             sum+=min;//sum累計道路長度，即是已選的權值
         }
         Ai[k]=0;//標誌為已選的邊的權值，避免重複選擇
         //例子：對比a到c和b到c的權值，取最小存進Ai[j]中
         for(j=0;j<S.count;j++){
            if(A[k][j]!=0&&A[k][j]<Ai[j]){
                 Ai[j]=A[k][j];
                 closest[j]=k;//點編號陣列，記錄下一條路的起點景點的編號
             }
         }
     }
     cout<<"*修建道路的總長度為："<<sum<<endl;
     returnMainFace();
}