图的操作和应用之景区信息管理系统

Gentleman

发布日期: 2019-09-20 07:15:32 浏览量: 803
评分：
star star star star star star star star star_border star_border
*转载请注明来自write-bug.com

一、功能要求

1.1 读文件创建图

  • 输入：从Vex.txt文件中读取景点信息，从Edge.txt文件中读取道路信息

  • 处理：根据读取的景区信息创建景区景点图

1.2 查询景点

  • 输入：想要查询的景点的编号

  • 处理：根据输入的景点编号，查询该景点及相邻景点的信息

  • 输出：

    • 景点名字
    • 景点介绍
    • 相邻景区的名字
    • 到达相邻景区的路径长度

1.3 旅游景点导航

  • 输入：起始景点的编号

  • 处理：使用深度优先搜索(DFS)算法，查询以该景点为起点，无回路游览整个景区的路线

  • 输出：所有符合要求的导航路线

1.4 搜索最短路径

  • 输入：

    • 起始景点的编号
    • 终点的编号

  • 处理：使用迪杰斯特拉(Dijkstra)算法，求得从起始景点到终点之间的最短路径，计算路径总长度

  • 输出：

    • 最短路线
    • 路径总长度

1.5 铺设电路规划

  • 处理：根据景区景点图使用普里姆(Prim)算法构造最小生成树，设计出一套铺设线路最短，但能满足每个景点都能通电的方案

  • 输出：

    • 需要铺设电路的道路
      -每条道路铺设电路的长度
    • 铺设电路的总长度

1.6 修改图保存文件

插入、删除、修改顶点、边的信息，注意顶点和边的关系，之后保存文件，重新读取文件建立图的存储结构并显示。

重点注意顶点和边的关系，考虑边是否重复？顶点是否存在？……

二、数据结构介绍

  1. #define MAX_SIZE 1000//最大可存顶点数
  2. #define INFINITY 99999//无穷大
  4. struct Vertex//顶点 
  5. {
  6.     int tag;//标记此顶点是否存在 
  7.     string name,info;
  8. };
  10. struct ArcNode 
  11. {
  12.     int n;
  13.     ArcNode *next;
  14. };
  16. struct VNode//邻接表 
  17. {
  18.     Vertex vex;
  19.     ArcNode *next;
  20. }AdjList[MAX_SIZE];
  22. struct Graph//图 
  23. {
  24.     int arc[MAX_SIZE][MAX_SIZE];//每个顶点与其余各个顶点之间边长
  25.     int vexnum;//目前顶点总数
  26.     int edgnum;//目前此图边总数
  27.     int maxvexno; //目前此图顶点最大编号
  28. }G;
  30. int created=0;//表示未创建图
  32. int main()//主函数
  33. {
  34.     int tag,m,n;
  35.     while(1)
  36.     {
  37.         tag=0;
  38.         Menu();
  39.         cin>>n;
  40.         switch(n)
  41.         {
  42.             case 1:CreatMap();break;
  43.             case 2:{cout<<"请输入景区编号："<<endl;cin>>n;SearchVex(n);}break;
  44.             case 3:{cout<<"请输入景区编号："<<endl;cin>>n;Navigation_DFS(n);}break;
  45.             case 4:{cout<<"请输入起止景区编号："<<endl;cin>>m>>n;ShortestPath_DIJ(m,n);}break;
  46.             case 5:WirePath_Prim();break;
  47.             case 6:Edit();break;
  48.             case 7:tag=1;break;
  49.             default:cout<<"更多功能正在开发，敬请期待……"<<endl;
  50.         }
  51.         if(tag)
  52.         break;
  53.     }
  54.     return 0;
  55. }
  57. void Menu()//主菜单 
  58. {
  59.     printf("---------------景区管理系统功能菜单---------------\n");
  60.     printf("1-----创建图\n");
  61.     printf("2-----查询景点信息\n");
  62.     printf("3-----旅游景点导航\n");
  63.     printf("4-----搜索最短路径\n");
  64.     printf("5-----铺设电路规划\n");
  65.     printf("6-----修改图\n"); 
  66.     printf("7-----退出主菜单\n"); 
  67.     printf("请输入功能序号执行功能：\n");
  68. }

三、功能实现

3.1 数据格式

  • Vex.txt中第一行景点总数，之后每一行一个景点信息，包括景点编号、名称、介绍
  • Edge.txt中每一行一条道路信息。包括景点编号、景点编号、道路距离

3.2 读文件创图

将文件中的数据读入内存，建立图的邻接表并输出图的邻接表。

3.2.1 实现代码

  1. void CreatMap()//导入文件数据创建图，并输出邻接表 
  2. {
  3.     int m,t,i,j;
  4.     //读取Vex.txt文件的景点信息 
  5.     fstream f1("./Vex.txt",ios::in); 
  6.     f1>>G.vexnum;
  7.     t=0;//记录已读取景点信息个数 
  8.     for(i=0;t<G.vexnum;i++)
  9.     {
  10.         f1>>m;
  11.         while(i!=m)
  12.         {
  13.             AdjList[i].vex.tag=0;//编号为i的景点不存在，标记为0 
  14.             i++;
  15.         }
  16.         AdjList[m].vex.tag=1; //景点存在，标记为1 
  17.         t++;
  18.         f1>>AdjList[m].vex.name>>AdjList[m].vex.info;//从vex.txt文件中读取景点信息 
  19.     }
  20.     G.maxvexno=m;//记录景点的最大编号 
  21.     f1.close();
  23.     //初始化各路径距离 
  24.     for(i=0;i<=G.maxvexno;i++)
  25.         if(AdjList[i].vex.tag)
  26.             for(j=0;j<=G.maxvexno;j++)
  27.                 if(AdjList[j].vex.tag)
  28.                     G.arc[i][j]=INFINITY;//初始化各景点间距离为INFINITY 
  30.     //读取Edge.txt的路径信息 
  31.     fstream f2("./Edge.txt",ios::in);
  32.     G.edgnum=0;
  33.     while(f2>>i>>j)
  34.     {
  35.         f2>>G.arc[i][j];
  36.         G.arc[j][i]=G.arc[i][j];//从Edge.txt文件中读取景点间距离，若文件中未出现两景点间距离则保持初始的INFINITY 
  37.         G.edgnum++;
  38.     }
  39.     f2.close();
  41.     created=1;//表示已经创建图 
  43.     //创建邻接表 
  44.     CreatAdjList(); 
  46.     //展示邻接表 
  47.     cout<<"邻接表如下："<<endl;//格式为V1->V2->V3 
  48.     for(i=0;i<=G.maxvexno;i++)
  49.         if(AdjList[i].vex.tag)
  50.         {
  51.             cout<<'V'<<i;
  52.             ArcNode *an=AdjList[i].next;
  53.             while(an)
  54.             {
  55.                 cout<<"->V"<<an->n;
  56.                 an=an->next;
  57.             }
  58.             cout<<endl;
  59.         }
  60. }
  62. void CreatAdjList()//建立邻接表 
  63. {
  64.     for(int i=0;i<=G.maxvexno;i++) 
  65.         if(AdjList[i].vex.tag)
  66.         {
  67.             ArcNode *a;
  68.             AdjList[i].next=NULL;
  69.             for(int j=G.maxvexno;j>=0;j--)
  70.                 if(AdjList[j].vex.tag)
  71.                     if(G.arc[i][j]<INFINITY)
  72.                     {
  73.                         a=new ArcNode;
  74.                         a->n=j;
  75.                         a->next=AdjList[i].next;
  76.                         AdjList[i].next=a;
  77.                     }
  78.         }
  79. }

3.2.2 数据格式

编号 名字 介绍
0 A区 风景优美，气候宜人。
1 B区 风景优美，气候宜人。
2 C区 风景优美，气候宜人。
3 D区 风景优美，气候宜人。
4 E区 风景优美，气候宜人。
5 F区 风景优美，气候宜人。
6 G区 风景优美，气候宜人。
景点1 景点2 距离(m)
A C 700
A E 1000
A F 600
B C 1000
B G 1000
C D 400
D E 300
D G 400
E F 600
F G 500

3.2.3 截图

3.3 查询景点

  • 输入：想要查询的景点的编号

处理：根据输入的景点编号，查询该景点及相邻景点的信息

  • 输出：

    • 景点名字
    • 景点介绍
    • 相邻景区的名字
    • 到达相邻景区的路径长度

  • 算法：根据输入编号直接用数组找到景点信息输出，再用邻接表找到与其相连的景点并输出信息

3.3.1 实现代码

  1. void SearchVex(int n)//查找编号为n的景点 
  2. {
  3.     if(created)//图已被创建 
  4.     { 
  5.         if(n<0||n>G.maxvexno||AdjList[n].vex.tag==0)//编号n不在文件读入的编号范围内或其标记为0 
  6.             cout<<"该景点不存在！"<<endl;
  7.         else
  8.         {//输出景点编号、名称和景点信息，以及相邻的各个景点编号、名称和相距距离 
  9.             cout<<n<" "<<AdjList[n].vex.name<<"  "<<AdjList[n].vex.info<<endl;
  10.             cout<<"相邻景点："<<endl;
  11.             for(int i=0;i<=G.maxvexno;i++)
  12.                 if(AdjList[i].vex.tag) 
  13.                     if(G.arc[i][n]<INFINITY)
  14.                         cout<<i<<"  "<<AdjList[i].vex.name<<"  "<<G.arc[i][n]<<endl; 
  15.         }
  16.     }
  17.     else//图未被创建 
  18.         cout<<"尚未读取文件创建图！"<<endl;
  19. }

3.3.2 截图

3.4 修改图保存文件

插入、删除、修改顶点、边的信息，注意顶点和边的关系，之后保存文件，重新读取文件建立图的存储结构并显示。

核心操作：首先要保证添加、删除后仍为连通图（因此添加景点也要添加一条边，删除顶点也要删除相连的边，代码中用IsConnected函数来判断是否连通），否则操作不能执行。其次在操作执行后都要将数据重新读入文件。最后要再一次读取文件创建图。

3.4.1 实现代码

  1. void Edit()//修改操作菜单
  2. {
  3.     int m;
  4.     if(created)
  5.     {
  6.         while(1)
  7.         {
  8.             int tag=0;
  9.             cout<<"-----编辑操作菜单-----"<<endl; 
  10.             cout<<"-----<1>添加-----"<<endl;
  11.             cout<<"-----<2>删除-----"<<endl;
  12.             cout<<"-----<3>修改-----"<<endl;
  13.             cout<<"-----<4>退出本菜单-----";
  14.             cout<<"输入编号执行相应操作："<<endl;
  15.             cin>>m;
  16.             switch(m)
  17.             {
  18.                 case 1:Add();break;
  19.                 case 2:Delete();break;
  20.                 case 3:Revise();break;    
  21.                 case 4:tag=1;break;
  22.                 default:cout<<"更多功能正在开发中，敬请期待……" <<endl;
  23.             } 
  24.             if(tag)
  25.                 break;
  26.         }
  27.     }
  28.     else
  29.         cout<<"尚未读取文件创建图！"<<endl;
  30. }
  32. int count;//记录已访问顶点数 
  34. int IsConnected()//判断是否为连通图
  35. {
  36.     count=0;
  37.     int *Visited=new int[G.maxvexno+1]; //标记是否已访问过 
  38.     for(int i=0;i<=G.maxvexno;i++)
  39.         if(AdjList[i].vex.tag)
  40.             Visited[i]=0;//初始化 
  41.     for(int i=0;i<=G.maxvexno;i++) 
  42.         if(AdjList[i].vex.tag)
  43.         {
  44.             Connect_DFS(i,Visited);
  45.             break;
  46.         }
  48.     if(count==G.vexnum)
  49.         return 1;//该图连通，返回1
  50.     else
  51.         return 0; //该图不连通，返回0
  52. }
  54. void Connect_DFS(int i,int *Visited)//DFS搜索
  55. {
  56.     ArcNode *an=AdjList[i].next;
  57.     Visited[i]=1;//标记已访问过 
  58.     count++;//并入已访问过的点集 
  59.     cout<<count<<endl;
  60.     while(an)//搜索与该顶点相连的每个顶点 
  61.     {
  62.         while(Visited[an->n]||AdjList[an->n].vex.tag==0)//已访问过就找下一个顶点 
  63.         {
  64.             an=an->next;
  65.             if(an==NULL)break;
  66.         }
  67.         if(an)
  68.         {
  69.             Connect_DFS(an->n,Visited);//对此顶点进行DFS搜索  
  70.             an=an->next;
  71.         }
  72.     }
  73. }
  75. void Add()//添加操作菜单 
  76. {
  77.     int n,tag;
  78.     while(1)
  79.     {
  80.         tag=0;
  81.         cout<<"Vex.txt内容读取："<<endl;
  82.         ShowVexTxt();
  83.         cout<<"Edge.txt内容读取："<<endl;
  84.         ShowEdgeTxt();
  85.         cout<<"--------添加选项------"<<endl;
  86.         cout<<"-----<1>景点-----" <<endl;
  87.         cout<<"-----<2>路径-----"<<endl;
  88.         cout<<"-----<3>退出当前菜单-----"<<endl; 
  89.         cout<<"输入功能序号执行相应功能："<<endl;
  90.         cin>>n;
  91.         switch(n)
  92.         {
  93.             case 1:AddVex();break;
  94.             case 2:AddEdge();break;
  95.             case 3:tag=1;break;
  96.             default:cout<<"更多功能正在开发，敬请期待……"<<endl;
  97.         }
  98.         if(tag)
  99.             break;
  100.     }
  101. }
  103. void AddVex()//添加景点 
  104. {
  105.     int no,start,end,dis,maxno;
  106.     string name,info;
  109.     if(G.vexnum<MAX_SIZE)
  110.     {
  111.         cout<<"请输入添加的景点及路径：（第一行：景点编号 名称 信息 第二行：景点编号 景点编号 距离）"<<endl;
  112.         cin>>no>>name>>info;
  113.         cin>>start>>end>>dis; 
  114.         if(no<0)
  115.             cout<<"景点编号不合法！添加失败！"<<endl;
  116.         else
  117.         {    
  118.             if(no>G.maxvexno||AdjList[no].vex.tag==0)
  119.             {//初始化该景点相关信息 
  120.                 AdjList[no].vex.tag=1; 
  121.                 AdjList[no].vex.name=name;
  122.                 AdjList[no].vex.info=info;
  123.                 G.vexnum++;
  124.                 maxno=G.maxvexno;
  125.                 if(no>G.maxvexno)//更改最大编号，并将不存在的顶点标记 
  126.                 {
  127.                     for(int i=G.maxvexno+1;i<no;i++)
  128.                         AdjList[i].vex.tag=0;
  129.                     G.maxvexno=no;
  130.                 }    
  131.                 for(int i=0;i<=G.maxvexno;i++)//初始化no与其他顶点的距离 
  132.                     if(AdjList[i].vex.tag)
  133.                     {
  134.                         G.arc[i][no]=INFINITY;
  135.                         G.arc[no][i]=INFINITY;
  136.                     }
  137.                 //添加道路 
  138.                 if(start<0||start>G.maxvexno||AdjList[start].vex.tag==0||end<0||end>G.maxvexno||AdjList[end].vex.tag==0)
  139.                     cout<<"景点不存在！添加失败！"<<endl;
  140.                 else if(dis<=0||dis>=INFINITY)
  141.                     cout<<"该路径距离超限！添加失败！"<<endl;
  142.                 else if(G.arc[start][end]<INFINITY)
  143.                     cout<<"该路径已记录！添加失败！"<<endl;
  144.                 else
  145.                 {
  146.                     G.arc[start][end]=dis;
  147.                     G.arc[end][start]=dis;
  148.                     G.edgnum++;
  149.                     CreatAdjList();//重建邻接表 
  150.                     if(IsConnected())//添加后仍是连通图 
  151.                     {
  152.                         fstream f3("./Vex.txt",ios::out); 
  153.                         fstream f4("./Edge.txt",ios::out);
  154.                         //读入Vex文件 
  155.                         f3<<G.vexnum<<endl; 
  156.                         for(int i=0;i<=G.maxvexno;i++)
  157.                             if(AdjList[i].vex.tag)
  158.                                 f3<<i<<' '<<AdjList[i].vex.name<<' '<<AdjList[i].vex.info<<endl;
  159.                         f3.close();
  160.                         //读入Edge文件
  161.                         for(int i=0;i<=G.maxvexno;i++) 
  162.                             if(AdjList[i].vex.tag)
  163.                                 for(int j=i;j<=G.maxvexno;j++)
  164.                                     if(AdjList[j].vex.tag)
  165.                                         if(G.arc[i][j]<INFINITY)
  166.                                             f4<<i<<' '<<j<<' '<<G.arc[i][j]<<endl;;
  167.                         f4.close(); 
  168.                         cout<<"添加景点成功！"<<endl;
  170.                     }
  171.                     else//否则添加失败 
  172.                     {//更改为添加前的值 
  173.                         AdjList[no].vex.tag=0; 
  174.                         G.vexnum--;
  175.                         G.maxvexno=maxno;
  176.                         G.arc[start][end]=INFINITY;
  177.                         G.arc[end][start]=INFINITY;
  178.                         G.edgnum--;
  179.                         cout<<"添加后为非连通图！添加失败！"<<endl;
  180.                     }
  181.                     //重新创建图 
  182.                     CreatMap();     
  183.                 }
  184.             }
  185.             else
  186.                 cout<<"该景点已存在！添加失败！"<<endl;
  187.         }
  188.     }
  189.     else
  190.         cout<<"景点存储数量已达上限，无法再添加！"<<endl;
  191. }
  193. void AddEdge()//添加道路
  194. {
  195.     int start,end,dis; 
  197.     //添加道路 
  198.     cout<<"请输入添加的路径：（景点编号 景点编号 距离）"<<endl;
  199.     cin>>start>>end>>dis; 
  200.     if(start<0||start>G.maxvexno||AdjList[start].vex.tag==0||end<0||end>G.maxvexno||AdjList[end].vex.tag==0)
  201.         cout<<"景点不存在！添加失败！"<<endl;
  202.     else if(dis<=0||dis>=INFINITY)
  203.         cout<<"该路径距离超限！添加失败！"<<endl;
  204.     else if(G.arc[start][end]<INFINITY)
  205.         cout<<"该路径已记录！添加失败！"<<endl;
  206.     else
  207.     {
  208.         G.arc[start][end]=dis;
  209.         G.arc[end][start]=dis;
  210.         G.edgnum++;
  211.         CreatAdjList();//重建邻接表 
  212.         if(IsConnected())//添加后仍是连通图 
  213.         {
  214.             fstream f5("./Edge.txt",ios::out);
  215.             //读入Edge文件
  216.             for(int i=0;i<=G.maxvexno;i++) 
  217.                 if(AdjList[i].vex.tag)
  218.                     for(int j=i;j<=G.maxvexno;j++)
  219.                         if(AdjList[j].vex.tag)
  220.                             if(G.arc[i][j]<INFINITY)
  221.                                 f5<<i<<' '<<j<<' '<<G.arc[i][j]<<endl;
  222.             f5.close();
  223.             cout<<"添加路径成功！"<<endl;
  224.         }
  225.         Else//添加后不是连通图
  226.         {//恢复原值
  227.             G.arc[start][end]=INFINITY;
  228.             G.arc[end][start]=INFINITY;
  229.             G.edgnum--;
  230.             cout<<"添加后为非连通图！添加失败！"<<endl;
  231.         }
  232.         CreatMap();//重新创建图 
  233.     }
  234. }

3.4.2 截图

  1. void Revise()//修改操作菜单 
  2. {
  3.     int n,tag;
  4.     while(1)
  5.     {
  6.         tag=0;
  7.         cout<<"Vex.txt内容读取："<<endl;
  8.         ShowVexTxt();
  9.         cout<<"Edge.txt内容读取："<<endl;
  10.         ShowEdgeTxt();
  11.         cout<<"--------修改选项------"<<endl;
  12.         cout<<"-----<1>景点-----" <<endl;
  13.         cout<<"-----<2>路径-----"<<endl;
  14.         cout<<"-----<3>退出当前菜单-----"<<endl; 
  15.         cout<<"请输入功能序号执行相应功能："<<endl; 
  16.         cin>>n;
  17.         switch(n)
  18.         {
  19.             case 1:ReviseVex();break;
  20.             case 2:ReviseEdge();break;
  21.             case 3:tag=1;break;
  22.             default:cout<<"更多功能正在开发，敬请期待……"<<endl;
  23.         }
  24.         if(tag)
  25.             break;
  26.     }    
  27. }
  29. void ReviseEdge()//修改道路距离
  30. {
  31.     //修改路径信息 
  32.     int m,n,start,end,dis;
  33.     cout<<"请输入要修改路径距离的路径个数：（不得超过"<<G.edgnum<<"个）"<<endl; 
  34.     cin>>n;
  35.     while(n<0||n>G.edgnum)
  36.     {
  37.         cout<<"已超过已存在路径个数！请重新输入："<<endl;
  38.         cin>>n;
  39.     }
  40.     m=n;
  41.     cout<<"请逐行输入路径新信息：（格式：景点编号 景点编号 距离）"<<endl;
  42.     while(n)
  43.     {
  44.         cin>>start>>end>>dis;
  45.         if(start<0||start>G.maxvexno||AdjList[start].vex.tag==0||end<0||end>G.maxvexno||AdjList[end].vex.tag==0)
  46.             cout<<"景点不存在！请重新输入修改信息："<<endl;
  47.         else if(dis<=0||dis>=INFINITY)
  48.             cout<<"该路径距离超限！请重新输入修改信息："<<endl;
  49.         else if(G.arc[start][end]==INFINITY)
  50.             cout<<"该路径不存在！请重新输入修改信息："<<endl;
  51.         else
  52.         {
  53.             G.arc[start][end]=dis;
  54.             G.arc[end][start]=dis; 
  55.             n--;
  56.         }
  57.     }
  59.     fstream f7("./Edge.txt",ios::out);
  60.     //读入文件 
  61.     for(int i=0;i<=G.maxvexno;i++)
  62.         if(AdjList[i].vex.tag)
  63.             for(int j=i;j<=G.maxvexno;j++)
  64.                 if(AdjList[j].vex.tag)
  65.                     if(G.arc[i][j]<INFINITY)
  66.                         f7<<i<<' '<<j<<' '<<G.arc[i][j]<<endl;
  67.     f7.close();
  68.     cout<<m<<"条路径信息已成功修改！"<<endl;
  70.     CreatMap();//重新创建图 
  71. }
  73. void ReviseVex()//修改景点信息
  74. {
  75.     int m,n,no;
  76.     string name,info;
  77.     //修改景点信息 
  78.     cout<<"请输入要修改的景点信息的景点个数：（不得超过"<<G.vexnum<<"个）"<<endl;
  79.     cin>>n;
  80.     while(n<0||n>G.vexnum)
  81.     {
  82.         cout<<"已超过目前已存在景点个数！请重新输入："<<endl;
  83.         cin>>n;
  84.     }
  85.     m=n;
  86.     cout<<"请逐行输入景点新信息：（格式：编号 景点名 介绍）"<<endl;
  87.     while(n)
  88.     {
  89.         cin>>no>>name>>info;
  90.         if(no>=0&&no<G.maxvexno&&AdjList[no].vex.tag)
  91.         {
  92.             AdjList[no].vex.name=name;
  93.             AdjList[no].vex.info=info;
  94.             n--;
  95.         }
  96.         else
  97.             cout<<"该景点不存在！请重输修改信息："<<endl;
  98.     }
  100.     //读入文件 
  101.     fstream f6("./Vex.txt",ios::out); 
  102.     f6<<G.vexnum<<endl;
  103.     for(int i=0;i<=G.maxvexno;i++)
  104.         if(AdjList[i].vex.tag)
  105.             f6<<i<<' '<<AdjList[i].vex.name<<' '<<AdjList[i].vex.info<<endl;
  106.     f6.close();
  107.     cout<<m<<"条景点信息已成功修改！"<<endl;
  109.     CreatMap();//重新创建图 
  110. }

  1. void Delete()//删除操作菜单
  2. {
  3.     int n,tag;
  4.     while(1)
  5.     {
  6.         tag=0;
  7.         cout<<"Vex.txt内容读取："<<endl;
  8.         ShowVexTxt();
  9.         cout<<"Edge.txt内容读取："<<endl;
  10.         ShowEdgeTxt();
  11.         cout<<"--------删除选项------"<<endl;
  12.         cout<<"-----<1>景点-----" <<endl;
  13.         cout<<"-----<2>路径-----"<<endl;
  14.         cout<<"-----<3>退出当前菜单-----"<<endl; 
  15.         cout<<"输入功能序号执行相应功能："<<endl; 
  16.         cin>>n;
  17.         switch(n)
  18.         {
  19.             case 1:DeleteVex();break;
  20.             case 2:DeleteEdge();break;
  21.             case 3:tag=1;break;
  22.             default:cout<<"更多功能正在开发，敬请期待……"<<endl;
  23.         }
  24.         if(tag)
  25.             break;
  26.     }
  27. }
  29. void DeleteVex()//删除景点
  30. {
  31.     int no,maxno;
  33.     cout<<"请输入要删除的编号："<<endl;
  34.     cin>>no;
  35.     if(no<0||no>G.maxvexno||AdjList[no].vex.tag==0)
  36.         cout<<"景点不存在！删除失败！"<<endl;
  37.     else
  38.     {
  39.         G.vexnum--;
  40.         AdjList[no].vex.tag=0;//修改标记 
  41.         maxno=G.maxvexno;
  42.         if(no==G.maxvexno)//更新最大编号 
  43.             for(int i=G.maxvexno-1;i>=0;i--)
  44.                 if(AdjList[i].vex.tag)
  45.                 {
  46.                     G.maxvexno=i;
  47.                     break;
  48.                 }
  49.         CreatAdjList();//重建邻接表 
  50.         if(IsConnected())
  51.         {//删除后连通
  52.             fstream f8("./Vex.txt",ios::out);
  53.             //读入Vex文件 
  54.             f8<<G.vexnum<<endl; 
  55.                 for(int i=0;i<=G.maxvexno;i++)
  56.                     if(AdjList[i].vex.tag)
  57.                         f8<<i<<' '<<AdjList[i].vex.name<<' '<<AdjList[i].vex.info<<endl;
  58.             f8.close();
  60.             fstream f9("./Edge.txt",ios::out);
  61.             //更新删除顶点后的路径并读入Edge文件 
  62.             G.edgnum=0;
  63.             for(int i=0;i<=G.maxvexno;i++)
  64.                 if(AdjList[i].vex.tag)
  65.                     for(int j=i;j<=G.maxvexno;j++)
  66.                         if(AdjList[j].vex.tag)
  67.                             if(G.arc[i][j]<INFINITY)
  68.                             {
  69.                                 f9<<i<<' '<<j<<' '<<G.arc[i][j]<<endl;
  70.                                 G.edgnum++;
  71.                             }
  72.             f9.close();
  73.             cout<<"成功删除景点！"<<endl;
  75.         }
  76.         else
  77.         {//不连通则恢复原值
  78.             G.vexnum++;
  79.             AdjList[no].vex.tag=1;//修改标记 
  80.             G.maxvexno=maxno;
  81.             cout<<"删除后为非连通图！删除失败！"<<endl; 
  82.         }
  84.         CreatMap();//重新创建图 
  85.     }
  86. } 
  88. void DeleteEdge()//删除道路
  89. { 
  90.     int n,m,dis,start,end;
  93.     //删除路径信息
  94.     cout<<"请输入要删除的路径个数：（不得超过"<<G.edgnum-G.vexnum+1<<"个）"<<endl;
  95.     cin>>n;
  96.     while(n<0||n>G.edgnum-G.vexnum+1)
  97.     {
  98.         cout<<"已超过可删除路径数限制！请重新输入："<<endl;
  99.         cin>>n;
  100.     }
  101.     m=n;
  102.     cout<<"请逐行输入路径连接的两景点：（格式：景点编号 景点编号）"<<endl;
  103.     while(n)
  104.     {
  105.         cin>>start>>end;
  106.         if(start<0||start>G.maxvexno||AdjList[start].vex.tag==0||end<0||end>G.maxvexno||AdjList[end].vex.tag==0)
  107.             cout<<"景点不存在！请重新输入删除信息："<<endl;
  108.         else if(G.arc[start][end]==INFINITY)
  109.             cout<<"该路径不存在！请重新输入删除信息："<<endl;
  110.         else
  111.         {
  112.             dis=G.arc[start][end];
  113.             G.arc[start][end]=INFINITY;
  114.             G.arc[end][start]=INFINITY;
  115.             G.edgnum--;
  116.             n--;
  117.             CreatAdjList();//重建邻接表 
  118.             if(IsConnected())
  119.             {//删除后仍连通
  120.                 fstream f10("./Edge.txt",ios::out); 
  121.                 //读入文件 
  122.                 for(int i=0;i<=G.maxvexno;i++)
  123.                     if(AdjList[i].vex.tag)
  124.                         for(int j=i;j<=G.maxvexno;j++)
  125.                             if(AdjList[j].vex.tag)
  126.                                 if(G.arc[i][j]<INFINITY)
  127.                                     f10<<i<<' '<<j<<' '<<G.arc[i][j]<<endl;
  128.                 f10.close();
  129.                 cout<<"成功删除路径！"<<endl;
  130.             } 
  131.             else
  132.             {//不连通则恢复原值
  133.                 G.arc[start][end]=dis;
  134.                 G.arc[end][start]=dis;
  135.                 G.edgnum++;
  136.                 cout<<"删除后为非连通图！删除失败！"<<endl;
  137.             }
  138.         }
  139.     }
  140.     cout<<m<<"条路径删除完毕！"<<endl;
  142.     CreatMap();//重新创建图     
  143. }

3.5 旅游景点导航

  • 输入：起始景点的编号

  • 处理：使用深度优先搜索(DFS)算法，查询以该景点为起点，无回路游览整个景区的路线

  • 输出：所有符合要求的导航路线

  • 算法：对DFS进行改良，对一个景点连接的所有景点都进行搜索，每一个都可以搜索出一条新路（用两个数组，一个数组用来标记本条路上访问过的景点，另一个数组标记搜索连接的景点中已搜索过的景点），以此递归，最终如果本条路上的景点数等于景点总数，说明该路无回路

3.5.1 代码实现

  1. void Navigation_DFS(int n)//DFS算法从编号为n的景点开始无回路遍历全图 
  2. {
  3.     if(created)//图已被创建 
  4.     { 
  5.         if(n<0||n>G.maxvexno||AdjList[n].vex.tag==0)//编号n不在文件读入的编号范围内或顶点标记为0 
  6.             cout<<"该景点不存在！"<<endl;
  7.         else
  8.         {
  9.             int count=1;//count记录本条路径已搜索过的顶点 
  10.             int *BVisited=new int[G.maxvexno+1];//横向标记 
  11.             int *DVisited=new int[G.maxvexno+1];//纵向标记 
  12.             int *no=new int[G.vexnum];//记录路径上的顶点编号 
  14.             for(int i=0;i<=G.maxvexno;i++)
  15.                 if(AdjList[i].vex.tag)
  16.                 {
  17.                     DVisited[i]=0;//复制前面纵向搜索的标记 
  18.                     BVisited[i]=0;//横向均未搜索过 
  19.                 }
  21.             no[0]=n;//记录起点 
  22.             DVisited[n]=1;//标记纵向已访问过 
  24.             ArcNode *an=AdjList[n].next;
  25.             while(an)//横向搜索与该顶点相连的每个顶点 
  26.             {
  27.                 while(BVisited[an->n])//横向或纵向已访问过就找下一个顶点 
  28.                 {
  29.                     an=an->next;
  30.                     if(an=NULL)break;
  31.                 }
  32.                 if(an)
  33.                 {
  34.                     DFS(an->n,count,DVisited,no);//对此顶点进行DFS搜索 
  35.                     BVisited[an->n]=1;//标记此顶点横向已访问过 
  36.                     an=an->next;
  37.                 }
  38.             }
  39.         }
  40.     }
  41.     else//图未被创建 
  42.         cout<<"尚未读取文件创建图！"<<endl;
  43. }
  45. void DFS(int n,int count,int *a,int *no)//DFS搜索路径 
  46. {
  47.     int *DVisited=new int[G.maxvexno+1];//纵向标记 
  48.     int *BVisited=new int[G.maxvexno+1];//横向标记 
  49.     for(int i=0;i<=G.maxvexno;i++)
  50.         if(AdjList[i].vex.tag)
  51.         {
  52.             DVisited[i]=a[i];//复制前面纵向搜索的标记 
  53.             BVisited[i]=0;//横向均未搜索过 
  54.         }
  56.     no[count++]=n;
  57.     DVisited[n]=1;//纵向标记已访问过 
  58.     ArcNode *an=AdjList[n].next;
  59.     while(an)//横向搜索与该顶点相连的每个顶点 
  60.     {
  61.         while(BVisited[an->n]||DVisited[an->n])//横向或纵向已访问过就找下一个顶点 
  62.         {
  63.             an=an->next;
  64.             if(an==NULL)break;
  65.         }
  66.         if(an)
  67.         {
  68.             DFS(an->n,count,DVisited,no);//对此顶点进行DFS搜索 
  69.             BVisited[an->n]=1;//标记此顶点横向已访问过 
  70.             an=an->next;
  71.         }
  72.     }
  74.     if(count==G.vexnum)//如果此路径上顶点数与总顶点数相同，说明该路径无回路 
  75.     {
  76.         for(int i=0;i<count-1;i++)//输出路径 
  77.             cout<<AdjList[no[i]].vex.name<<"-->";
  78.         cout<<AdjList[count-1].vex.name<<endl;
  79.     }
  80. }

3.5.2 截图

DFS核心代码流程图

3.6 搜索最短路径

  • 输入：

    • 起始景点的编号
    • 终点的编号

  • 处理：使用迪杰斯特拉(Dijkstra)算法，求得从起始景点到终点之间的最短路径，计算路径总长度

  • 输出：

    • 最短路线
    • 路径总长度

  • 算法：先用Dijkstra算法，然后根据两个景点编号输出其最短路径。优点是可以找到任意两点间最短路径，缺点是遍历的节点太多，效率很低

3.6.1 代码实现

  1. void ShortestPath_DIJ(int m,int n)//Dijkstra算法求编号m景区到编号n景区的最短路线 
  2. {
  3.     if(created)
  4.     {
  5.         if(m<0||m>G.maxvexno||AdjList[m].vex.tag==0||n<0||n>G.maxvexno||AdjList[n].vex.tag==0)
  6.             cout<<"景点不存在"<<endl;
  7.         else
  8.         {
  9.             int *Pre=new int[G.maxvexno+1];//记录当前顶点的前一顶点 
  10.             int *Dis=new int[G.maxvexno+1];//起点到各个顶点的当前最短距离 
  11.             int *final=new int[G.maxvexno+1];// 记录是否已找到起点到各个顶点的最短路径 
  13.             for(int i=0;i<=G.maxvexno;i++)//初始化 
  14.                 if(AdjList[i].vex.tag)
  15.                 {
  16.                     final[i]=0;//表示起点到各个顶点的最短距离均未找到 
  17.                     Dis[i]=G.arc[m][i];//初始化起点到各个顶点的最短距离，与起点相连的就是连线的距离，否则就是INFINITY 
  18.                     if(Dis[i]<INFINITY)
  19.                         Pre[i]=m;//最短距离小于INFINITY，表明与起点相连，则其前一顶点为起点 
  20.                     else
  21.                         Pre[i]=-1;//否则置为-1，表示无前一顶点 
  22.                 }
  23.             Dis[m]=0;//起点到自身距离为0 
  24.             final[m]=1;//起点到起点已找到最短路径 
  26.             for(int i=0;i<=G.maxvexno;i++)
  27.                 if(AdjList[i].vex.tag)
  28.                 {
  29.                     int min=INFINITY;//记录离起点最近的距离 
  30.                     int v=-1;//记录离起点最近的点 
  31.                     for(int j=1;j<=G.maxvexno;j++)//从未找到最短路径的顶点中找到离起点最近的顶点 
  32.                         if(AdjList[j].vex.tag)
  33.                             if(!final[j]&&Dis[j]<min)
  34.                             {
  35.                                 min=Dis[j];
  36.                                 v=j; 
  37.                             } 
  38.                     final[v]=1;//起点到该点已找到最短距离 
  39.                     for(int j=0;j<=G.maxvexno;j++)
  40.                         if(AdjList[j].vex.tag)
  41.                             if(!final[j]&&(min+G.arc[v][j]<Dis[j]))//更新起点到各点的最短距离 
  42.                             {
  43.                                 Dis[j]=min+G.arc[v][j];
  44.                                 Pre[j]=v;//记录前一顶点 
  45.                             }
  46.                 }
  48.             cout<<"从"<<AdjList[m].vex.name<<"至"<<AdjList[n].vex.name; 
  49.             if(Dis[n]<INFINITY)//倒序输出路径 
  50.             {
  51.                 cout<<"最短路径总长度为"<<Dis[n]<<"  最短路径(倒序)如下："<<endl; 
  52.                 cout<<AdjList[n].vex.name;
  53.                 int v=Pre[n];
  54.                 while(v!=m)
  55.                 {
  56.                     cout<<"<--"<<AdjList[v].vex.name;
  57.                     v=Pre[v];
  58.                 }
  59.                 cout<<"<--"<<AdjList[m].vex.name<<endl;
  60.             }
  61.             else
  62.                 cout<<"不通！"<<endl;
  63.         }
  64.     }
  65.     else//图未被创建 
  66.         cout<<"尚未读取文件创建图！"<<endl;
  67. }

3.6.2 截图

核心代码流程图

3.7 铺设电路规划

  • 处理：根据景区景点图使用普里姆(Prim)算法构造最小生成树，设计出一套铺设线路最短，但能满足每个景点都能通电的方案

  • 输出：

    • 需要铺设电路的道路
    • 每条道路铺设电路的长度
    • 铺设电路的总长度

  • 算法：Prim算法，适用于边数多的图

3.7.1 代码实现

  1. void WirePath_Prim()//Prim算法求铺设最短电路 
  2. {
  3.     struct
  4.     {
  5.         int vexno;
  6.         int lowcost;
  7.     }closedge[MAX_SIZE];//记录当前已经确定的点集到某顶点i的最短距离及对应顶点编号 
  9.     int sum=0;//总长度
  10.     int t;//记录一个顶点编号，以此顶点为起点 
  12.     for(int i=0;i<=G.maxvexno;i++)//找t 
  13.         if(AdjList[i].vex.tag)
  14.         {
  15.             t=i;
  16.             break;
  17.         }
  19.     for(int i=0;i<=G.maxvexno;i++)//初始化已确定点集仅含t 
  20.         if(AdjList[i].vex.tag)
  21.         {
  22.             closedge[i].vexno=t;
  23.             closedge[i].lowcost=G.arc[t][i];
  24.         }
  25.     closedge[t].lowcost=0;//表示该顶点属于已确定点集 
  27.     for(int i=1;i<=G.vexnum;i++)//将其余G.vexnum-1个顶点并入已确定点集中 
  28.     {
  29.         int vex2=-1,vex1=-1,min=INFINITY;
  30.         for(int j=0;j<=G.maxvexno;j++)//找与已确定点集距离最近的顶点 
  31.             if(AdjList[j].vex.tag)
  32.                 if(closedge[j].lowcost>0&&closedge[j].lowcost<INFINITY)
  33.                     if(closedge[j].lowcost<min)
  34.                     {
  35.                         min=closedge[j].lowcost;
  36.                         vex2=j;
  37.                         vex1=closedge[j].vexno;//与该顶点相连的已确定点集中的某一顶点 
  38.                     }
  40.         if(vex1==-1&&vex2==-1)//搜索结束 
  41.             break;
  43.         cout<<AdjList[vex1].vex.name<<"-->"<<AdjList[vex2].vex.name<<"  "<<min<<endl;//输出最短距离及连接的两点 
  44.         closedge[vex2].lowcost=0;//将该顶点并入已确定点集 
  46.         sum+=min;//总长度更新 
  47.         for(int j=0;j<=G.maxvexno;j++)//更新已确定点集到各顶点的最短距离 
  48.             if(G.arc[vex2][j]<closedge[j].lowcost)
  49.             {
  50.                 closedge[j].vexno=vex2;
  51.                 closedge[j].lowcost=G.arc[vex2][j];
  52.             }
  53.     }
  54.     cout<<"电路总长："<<sum<<endl;//输出电路总长 
  55. }

3.7.2 截图

核心代码流程图

四、总结

首先对DFS、迪杰斯特拉、Prim算法都再次深入理解了一遍，而且能更加熟练的运用和修改后适用于新问题，同时也对算法的利弊有所体会。

再一个就是学会了使用文件的读取和读写流，文件数据修改后应该重新写入文件，以及重新创建相应的图。

这个过程中，一个很重要的问题还是指针的熟练掌握和运用，对于所创建的数据结构必要时要在数据的末尾指针赋空，这样检索遍历时不会混乱。

在刚开始程序写完运行的时候很容易出现烫烫烫，就是因为传值没有传过来，数据没有初始化等原因。

另外，通过设计这个程序，让我对于程序的整体性、容错性以及尽可能让软件输入简洁明了有了更深的认识，尽可能让用户输入正确的数据，这样才能保证程序不会因为用户输错数据类型而崩溃；其次还有用户输入的数据必须有效，这就需要代码去识别，如果无效必须进行处理，否则也会引起崩溃。

主要考察的修改操作这一块，要求很强的逻辑性，必须处理好修改成功与否与文件是否重新读写的关系。因为整个程序是在连通图的大前提下，所以无论哪一步操作都要注意操作后图是否连通，如果连通方可修改，否则不能执行操作。修改后还要对应重新读写文件创建新图。

总之，在写程序时要全面考虑，不管要考虑需求，还要对程序的容错性最大限度地考虑到，保证程序在用户输错数据的情况下依然能够正常运行。

上传的附件 cloud_download 图的操作和应用之景区信息管理系统.7z ( 1.24mb, 9次下载 )
error_outline 下载需要10点积分

keyboard_arrow_left上一篇 : 基于MFC实现的基本门电路的绘制与连接 基于Keras和tensorflow深度学习Python实现的支持人脸识别和情绪分类的社区APP网站和微信小程序 : 下一篇keyboard_arrow_right

comment 1
Gentleman
2019-09-20 07:15:23
图的操作和应用之景区信息管理系统
mode_comment 评论(0)

Gentleman

发送私信

一个人幸运的前提，其实是ta有能力改变自己

12
文章数
24
评论数
最近文章
highlight comment

Copyright @2020-WRITE-BUG.COM 技术支持 - YCY科技 - 备案/许可证编号：京ICP备16025663号-5

eject