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

Gentleman

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

三、功能实现

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();
  22. //初始化各路径距离
  23. for(i=0;i<=G.maxvexno;i++)
  24. if(AdjList[i].vex.tag)
  25. for(j=0;j<=G.maxvexno;j++)
  26. if(AdjList[j].vex.tag)
  27. G.arc[i][j]=INFINITY;//初始化各景点间距离为INFINITY
  28. //读取Edge.txt的路径信息
  29. fstream f2("./Edge.txt",ios::in);
  30. G.edgnum=0;
  31. while(f2>>i>>j)
  32. {
  33. f2>>G.arc[i][j];
  34. G.arc[j][i]=G.arc[i][j];//从Edge.txt文件中读取景点间距离,若文件中未出现两景点间距离则保持初始的INFINITY
  35. G.edgnum++;
  36. }
  37. f2.close();
  38. created=1;//表示已经创建图
  39. //创建邻接表
  40. CreatAdjList();
  41. //展示邻接表
  42. cout<<"邻接表如下:"<<endl;//格式为V1->V2->V3
  43. for(i=0;i<=G.maxvexno;i++)
  44. if(AdjList[i].vex.tag)
  45. {
  46. cout<<'V'<<i;
  47. ArcNode *an=AdjList[i].next;
  48. while(an)
  49. {
  50. cout<<"->V"<<an->n;
  51. an=an->next;
  52. }
  53. cout<<endl;
  54. }
  55. }
  56. void CreatAdjList()//建立邻接表
  57. {
  58. for(int i=0;i<=G.maxvexno;i++)
  59. if(AdjList[i].vex.tag)
  60. {
  61. ArcNode *a;
  62. AdjList[i].next=NULL;
  63. for(int j=G.maxvexno;j>=0;j--)
  64. if(AdjList[j].vex.tag)
  65. if(G.arc[i][j]<INFINITY)
  66. {
  67. a=new ArcNode;
  68. a->n=j;
  69. a->next=AdjList[i].next;
  70. AdjList[i].next=a;
  71. }
  72. }
  73. }

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

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. }
  28. void ReviseEdge()//修改道路距离
  29. {
  30. //修改路径信息
  31. int m,n,start,end,dis;
  32. cout<<"请输入要修改路径距离的路径个数:(不得超过"<<G.edgnum<<"个)"<<endl;
  33. cin>>n;
  34. while(n<0||n>G.edgnum)
  35. {
  36. cout<<"已超过已存在路径个数!请重新输入:"<<endl;
  37. cin>>n;
  38. }
  39. m=n;
  40. cout<<"请逐行输入路径新信息:(格式:景点编号 景点编号 距离)"<<endl;
  41. while(n)
  42. {
  43. cin>>start>>end>>dis;
  44. if(start<0||start>G.maxvexno||AdjList[start].vex.tag==0||end<0||end>G.maxvexno||AdjList[end].vex.tag==0)
  45. cout<<"景点不存在!请重新输入修改信息:"<<endl;
  46. else if(dis<=0||dis>=INFINITY)
  47. cout<<"该路径距离超限!请重新输入修改信息:"<<endl;
  48. else if(G.arc[start][end]==INFINITY)
  49. cout<<"该路径不存在!请重新输入修改信息:"<<endl;
  50. else
  51. {
  52. G.arc[start][end]=dis;
  53. G.arc[end][start]=dis;
  54. n--;
  55. }
  56. }
  57. fstream f7("./Edge.txt",ios::out);
  58. //读入文件
  59. for(int i=0;i<=G.maxvexno;i++)
  60. if(AdjList[i].vex.tag)
  61. for(int j=i;j<=G.maxvexno;j++)
  62. if(AdjList[j].vex.tag)
  63. if(G.arc[i][j]<INFINITY)
  64. f7<<i<<' '<<j<<' '<<G.arc[i][j]<<endl;
  65. f7.close();
  66. cout<<m<<"条路径信息已成功修改!"<<endl;
  67. CreatMap();//重新创建图
  68. }
  69. void ReviseVex()//修改景点信息
  70. {
  71. int m,n,no;
  72. string name,info;
  73. //修改景点信息
  74. cout<<"请输入要修改的景点信息的景点个数:(不得超过"<<G.vexnum<<"个)"<<endl;
  75. cin>>n;
  76. while(n<0||n>G.vexnum)
  77. {
  78. cout<<"已超过目前已存在景点个数!请重新输入:"<<endl;
  79. cin>>n;
  80. }
  81. m=n;
  82. cout<<"请逐行输入景点新信息:(格式:编号 景点名 介绍)"<<endl;
  83. while(n)
  84. {
  85. cin>>no>>name>>info;
  86. if(no>=0&&no<G.maxvexno&&AdjList[no].vex.tag)
  87. {
  88. AdjList[no].vex.name=name;
  89. AdjList[no].vex.info=info;
  90. n--;
  91. }
  92. else
  93. cout<<"该景点不存在!请重输修改信息:"<<endl;
  94. }
  95. //读入文件
  96. fstream f6("./Vex.txt",ios::out);
  97. f6<<G.vexnum<<endl;
  98. for(int i=0;i<=G.maxvexno;i++)
  99. if(AdjList[i].vex.tag)
  100. f6<<i<<' '<<AdjList[i].vex.name<<' '<<AdjList[i].vex.info<<endl;
  101. f6.close();
  102. cout<<m<<"条景点信息已成功修改!"<<endl;
  103. CreatMap();//重新创建图
  104. }

  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. }
  28. void DeleteVex()//删除景点
  29. {
  30. int no,maxno;
  31. cout<<"请输入要删除的编号:"<<endl;
  32. cin>>no;
  33. if(no<0||no>G.maxvexno||AdjList[no].vex.tag==0)
  34. cout<<"景点不存在!删除失败!"<<endl;
  35. else
  36. {
  37. G.vexnum--;
  38. AdjList[no].vex.tag=0;//修改标记
  39. maxno=G.maxvexno;
  40. if(no==G.maxvexno)//更新最大编号
  41. for(int i=G.maxvexno-1;i>=0;i--)
  42. if(AdjList[i].vex.tag)
  43. {
  44. G.maxvexno=i;
  45. break;
  46. }
  47. CreatAdjList();//重建邻接表
  48. if(IsConnected())
  49. {//删除后连通
  50. fstream f8("./Vex.txt",ios::out);
  51. //读入Vex文件
  52. f8<<G.vexnum<<endl;
  53. for(int i=0;i<=G.maxvexno;i++)
  54. if(AdjList[i].vex.tag)
  55. f8<<i<<' '<<AdjList[i].vex.name<<' '<<AdjList[i].vex.info<<endl;
  56. f8.close();
  57. fstream f9("./Edge.txt",ios::out);
  58. //更新删除顶点后的路径并读入Edge文件
  59. G.edgnum=0;
  60. for(int i=0;i<=G.maxvexno;i++)
  61. if(AdjList[i].vex.tag)
  62. for(int j=i;j<=G.maxvexno;j++)
  63. if(AdjList[j].vex.tag)
  64. if(G.arc[i][j]<INFINITY)
  65. {
  66. f9<<i<<' '<<j<<' '<<G.arc[i][j]<<endl;
  67. G.edgnum++;
  68. }
  69. f9.close();
  70. cout<<"成功删除景点!"<<endl;
  71. }
  72. else
  73. {//不连通则恢复原值
  74. G.vexnum++;
  75. AdjList[no].vex.tag=1;//修改标记
  76. G.maxvexno=maxno;
  77. cout<<"删除后为非连通图!删除失败!"<<endl;
  78. }
  79. CreatMap();//重新创建图
  80. }
  81. }
  82. void DeleteEdge()//删除道路
  83. {
  84. int n,m,dis,start,end;
  85. //删除路径信息
  86. cout<<"请输入要删除的路径个数:(不得超过"<<G.edgnum-G.vexnum+1<<"个)"<<endl;
  87. cin>>n;
  88. while(n<0||n>G.edgnum-G.vexnum+1)
  89. {
  90. cout<<"已超过可删除路径数限制!请重新输入:"<<endl;
  91. cin>>n;
  92. }
  93. m=n;
  94. cout<<"请逐行输入路径连接的两景点:(格式:景点编号 景点编号)"<<endl;
  95. while(n)
  96. {
  97. cin>>start>>end;
  98. if(start<0||start>G.maxvexno||AdjList[start].vex.tag==0||end<0||end>G.maxvexno||AdjList[end].vex.tag==0)
  99. cout<<"景点不存在!请重新输入删除信息:"<<endl;
  100. else if(G.arc[start][end]==INFINITY)
  101. cout<<"该路径不存在!请重新输入删除信息:"<<endl;
  102. else
  103. {
  104. dis=G.arc[start][end];
  105. G.arc[start][end]=INFINITY;
  106. G.arc[end][start]=INFINITY;
  107. G.edgnum--;
  108. n--;
  109. CreatAdjList();//重建邻接表
  110. if(IsConnected())
  111. {//删除后仍连通
  112. fstream f10("./Edge.txt",ios::out);
  113. //读入文件
  114. for(int i=0;i<=G.maxvexno;i++)
  115. if(AdjList[i].vex.tag)
  116. for(int j=i;j<=G.maxvexno;j++)
  117. if(AdjList[j].vex.tag)
  118. if(G.arc[i][j]<INFINITY)
  119. f10<<i<<' '<<j<<' '<<G.arc[i][j]<<endl;
  120. f10.close();
  121. cout<<"成功删除路径!"<<endl;
  122. }
  123. else
  124. {//不连通则恢复原值
  125. G.arc[start][end]=dis;
  126. G.arc[end][start]=dis;
  127. G.edgnum++;
  128. cout<<"删除后为非连通图!删除失败!"<<endl;
  129. }
  130. }
  131. }
  132. cout<<m<<"条路径删除完毕!"<<endl;
  133. CreatMap();//重新创建图
  134. }

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];//记录路径上的顶点编号
  13. for(int i=0;i<=G.maxvexno;i++)
  14. if(AdjList[i].vex.tag)
  15. {
  16. DVisited[i]=0;//复制前面纵向搜索的标记
  17. BVisited[i]=0;//横向均未搜索过
  18. }
  19. no[0]=n;//记录起点
  20. DVisited[n]=1;//标记纵向已访问过
  21. ArcNode *an=AdjList[n].next;
  22. while(an)//横向搜索与该顶点相连的每个顶点
  23. {
  24. while(BVisited[an->n])//横向或纵向已访问过就找下一个顶点
  25. {
  26. an=an->next;
  27. if(an=NULL)break;
  28. }
  29. if(an)
  30. {
  31. DFS(an->n,count,DVisited,no);//对此顶点进行DFS搜索
  32. BVisited[an->n]=1;//标记此顶点横向已访问过
  33. an=an->next;
  34. }
  35. }
  36. }
  37. }
  38. else//图未被创建
  39. cout<<"尚未读取文件创建图!"<<endl;
  40. }
  41. void DFS(int n,int count,int *a,int *no)//DFS搜索路径
  42. {
  43. int *DVisited=new int[G.maxvexno+1];//纵向标记
  44. int *BVisited=new int[G.maxvexno+1];//横向标记
  45. for(int i=0;i<=G.maxvexno;i++)
  46. if(AdjList[i].vex.tag)
  47. {
  48. DVisited[i]=a[i];//复制前面纵向搜索的标记
  49. BVisited[i]=0;//横向均未搜索过
  50. }
  51. no[count++]=n;
  52. DVisited[n]=1;//纵向标记已访问过
  53. ArcNode *an=AdjList[n].next;
  54. while(an)//横向搜索与该顶点相连的每个顶点
  55. {
  56. while(BVisited[an->n]||DVisited[an->n])//横向或纵向已访问过就找下一个顶点
  57. {
  58. an=an->next;
  59. if(an==NULL)break;
  60. }
  61. if(an)
  62. {
  63. DFS(an->n,count,DVisited,no);//对此顶点进行DFS搜索
  64. BVisited[an->n]=1;//标记此顶点横向已访问过
  65. an=an->next;
  66. }
  67. }
  68. if(count==G.vexnum)//如果此路径上顶点数与总顶点数相同,说明该路径无回路
  69. {
  70. for(int i=0;i<count-1;i++)//输出路径
  71. cout<<AdjList[no[i]].vex.name<<"-->";
  72. cout<<AdjList[count-1].vex.name<<endl;
  73. }
  74. }

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

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的最短距离及对应顶点编号
  8. int sum=0;//总长度
  9. int t;//记录一个顶点编号,以此顶点为起点
  10. for(int i=0;i<=G.maxvexno;i++)//找t
  11. if(AdjList[i].vex.tag)
  12. {
  13. t=i;
  14. break;
  15. }
  16. for(int i=0;i<=G.maxvexno;i++)//初始化已确定点集仅含t
  17. if(AdjList[i].vex.tag)
  18. {
  19. closedge[i].vexno=t;
  20. closedge[i].lowcost=G.arc[t][i];
  21. }
  22. closedge[t].lowcost=0;//表示该顶点属于已确定点集
  23. for(int i=1;i<=G.vexnum;i++)//将其余G.vexnum-1个顶点并入已确定点集中
  24. {
  25. int vex2=-1,vex1=-1,min=INFINITY;
  26. for(int j=0;j<=G.maxvexno;j++)//找与已确定点集距离最近的顶点
  27. if(AdjList[j].vex.tag)
  28. if(closedge[j].lowcost>0&&closedge[j].lowcost<INFINITY)
  29. if(closedge[j].lowcost<min)
  30. {
  31. min=closedge[j].lowcost;
  32. vex2=j;
  33. vex1=closedge[j].vexno;//与该顶点相连的已确定点集中的某一顶点
  34. }
  35. if(vex1==-1&&vex2==-1)//搜索结束
  36. break;
  37. cout<<AdjList[vex1].vex.name<<"-->"<<AdjList[vex2].vex.name<<" "<<min<<endl;//输出最短距离及连接的两点
  38. closedge[vex2].lowcost=0;//将该顶点并入已确定点集
  39. sum+=min;//总长度更新
  40. for(int j=0;j<=G.maxvexno;j++)//更新已确定点集到各顶点的最短距离
  41. if(G.arc[vex2][j]<closedge[j].lowcost)
  42. {
  43. closedge[j].vexno=vex2;
  44. closedge[j].lowcost=G.arc[vex2][j];
  45. }
  46. }
  47. cout<<"电路总长:"<<sum<<endl;//输出电路总长
  48. }

3.7.2 截图

核心代码流程图

四、总结

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

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

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

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

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

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

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

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

发送私信

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

8
文章数
23
评论数
eject