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<<"*形成的导游线路图（采取深度优先策略）如下所示：\n\n\t";
     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();
}