基于C++实现的公交线路多重图（图的数据结构与算法实现）.zip

# 图 ## 1. 实验目的 1. 掌握图的定义和图的邻接表存储结构； 2. 掌握图的创建方法； 3. 掌握顶点和边的操作； 4. 掌握图的基本算法并能实际应用； 5. 掌握图的深度优先搜索算法以及实现方法； 6. 使用C/C++语言和图实现“公交线路图”专题。 ## 2. 实验环境 **硬件**：Intel Core i5 8300H CPU 2.30GHZ **软件**：Windows 10 64bit操作系统，编译环境 Visual Studio 2019 ## 3. 实验内容 程序为控制台程序,使用图数据结构和算法,开始运行时,输出菜单,供用户选择。具体实现的功能如下： - 创建公交线路图输入站点和公交线路数据,程序根据站点信息和线路信息创建公交线路图。 - 站点信息集合(编号、名字)。 - 公交线路信息集合(线路编号,线路两端站点编号,路段长度)。 - 查询公交线路和站点信息 为验证公交线路图是否创建成功,程序需实现查询公交线路和站点信息功能。 - 查询公交线路:输入公交线路编号,系统通过公交线路编号查找到该线路途经的所有站点并输出。 - 查询站点信息:输人站点编号,系统通过站点编号查找到所有经过该站点的公交线路并输出。 - 查询两站点之间的路线,找到至多换乘1次的路线,并输出结果 用户输人要查询的起点和终点,程序先判断两个站点之间是否有一条路径（即两个站点之间是否连通)。若两个站点之间有路线,则找到所有最多换乘1次的路线,然后依次输出,如图1-39所示。共找到N条路线,如图1-40所示 - 提示共找到几条路线:从|起点站名|到|终点站名|共找到N条路线,如图1-40所示。 - 循环依次输出每条路线,有路线编号和站点与公交信息。依次输出路线中经过的每一站,并在站点与站点之间输出两站之间所坐的公交车名,如图1-41所示。 - 若两个站点之间没有可以找到的路线,则提示用户“两站点之间没有公交路线!”,如图1-42所示。若两个站点之间有路线,但是不满足最多换乘1.次的条件,则提示用户“没有满足条件的路线!”,如图1-43所示。 ## 4. 实验程序 ### 4.1 程序源代码 #### 文件名：main.cpp ```c++ # include "dialog.h" int main() { Dialog(R"(D:\Projects\AlgorithmLab\e4\test_data.txt)") .begin_dialog(); } ``` #### 文件名：dialog.h ```c++ # ifndef _DIALOG_H_ # define _DIALOG_H_ # include "map.h" /// 负责UI层的互动 class Dialog { Map map; /// 查询公交线路 void query_bus(); /// 查询两点间的全部路径 void query_path(); /// 查询经过车站的公交线路 void query_stop(); public: Dialog(const char* file_name); Dialog(const Map& map); void begin_dialog(); }; # endif // _DIALOG_H_ ``` #### 文件名：map_scanner.h ```c++ # ifndef _MAP_SCANNER_H_ # define _MAP_SCANNER_H_ # include <iostream> # include "map.h" /// 从文件流读取地图 class MapScanner { public: Map scan(std::istream& s); }; # endif // _MAP_SCANNER_H_ ``` #### 文件名：map.h ```c++ # ifndef _ADJACENCY_LIST_H_ # define _ADJACENCY_LIST_H_ # include <list> # include <vector> # include <string> /// 顶点索引 using VertexIndex = int; /// 公交线路索引 using BusIndex = int; /// 边的额外数据 struct EdgeAddtionalData { /// 长度 double length = -1; /// 属于哪个公交 BusIndex bus_index = -1; EdgeAddtionalData() {}; EdgeAddtionalData(double length, BusIndex bus_index) :length(length), bus_index(bus_index) {} }; /// 顶点的额外数据 struct VertexAddtionalData { /// 顶点（车站）的名字 std::string name; VertexAddtionalData() {} VertexAddtionalData(const std::string& name) :name(name) {} }; /// 边 struct Edge { /// 尾点的索引 VertexIndex tail; /// 额外数据 EdgeAddtionalData data; Edge(VertexIndex tail, EdgeAddtionalData data) : tail(tail), data(data) {} }; /// 顶点 struct Vertex { /// 所有以它为起始点的边 std::list<Edge> edges; VertexAddtionalData data; Vertex() {} Vertex(const std::string& name) :data(VertexAddtionalData(name)) {} Vertex(const VertexAddtionalData& data) :data(data) {} }; /// 公交线路信息 struct BusInfo { /// 公交车名称 std::string name; /// 公交车起始站 VertexIndex start; BusInfo() {} BusInfo(const std::string& name, VertexIndex start) :name(name), start(start) {} }; /// 地图 class Map { /// 邻接链表 std::vector<Vertex> vertex_adjacency; /// 所有公交线路 std::vector<BusInfo> buses; /// 深度优先搜索 void dfs(VertexIndex src, VertexIndex dest , std::vector<bool>& visited , std::vector<Edge>& local_path , std::vector<std::vector<Edge>>& res); public: /// 添加顶点 VertexIndex add_vertex(std::string name); /// 添加边 void add_edge(VertexIndex vstart, VertexIndex vend, EdgeAddtionalData edge_data); /// 添加公交线 BusIndex add_bus(BusInfo info); /// 根据名字找公交线 BusIndex find_bus(const std::string& bus_name); /// 根据名字找顶点（公交站） VertexIndex find_vertex(const std::string& name); /// 根据索引取得公交信息 BusInfo get_bus_info(BusIndex i); /// 根据索引取得顶点（公交站）信息 VertexAddtionalData get_vertex_data(VertexIndex i); /// 沿着公交线找到所有顶点 std::vector<VertexIndex> track_down_bus(BusIndex bus); /// 找两点之间的所有路径 std::vector<std::vector<Edge>> search_paths(VertexIndex a, VertexIndex b); /// 尾为该顶点的边 std::vector<Edge> inbound_edges(VertexIndex v); /// 头为该顶点的边 std::vector<Edge> outbound_edges(VertexIndex v); }; # endif // _ADJACENCY_LIST_H_ ``` #### **文件名：dialog.cpp** ```c++ # include "dialog.h" # include "map_scanner.h" # include <iostream> # include <fstream> Dialog::Dialog(const char* file_name) { std::cout << "Loading map from " << file_name << std::endl; MapScanner scanner; map = scanner.scan(std::ifstream(R"(D:\Projects\AlgorithmLab\e4\test_data.txt)")); std::cout << "Map loaded!" << std::endl; } Dialog::Dialog(const Map& map) :map(map) {} void Dialog::begin_dialog() { int number = 0; while (true) { std::cout << "Hi, what do you want me to do?" << std::endl; std::cout << "1: Show bus route." << std::endl; std::cout << "2: Find paths from A to B." << std::endl; std::cout << "3: Show bus stop info." << std::endl; std::cout << "0: Exit." << std::endl; std::cout << "Enter a number:" << std::endl; std::cout << ">>> "; std::cin >> number; if (number == 0) { return; } else if (number == 1) { query_bus(); } else if (number == 2) { query_path(); } else if (number == 3) { query_stop(); } std::cout << std::endl; } } void Dialog::query_bus() { std::string bus_name; std::cout << "Which bus? Tell me its name:" << std::endl; std::cout << ">>> "; std::cin >> bus_name; BusIndex bi = map.find_bus(bus_name); if (bi != -1) { std::vector<VertexIndex> path = map.track_down_bus(bi); for (int i = 0; i < path.size(); i++) { if (i != 0) { std::cout << " -> "; } std::cout << map.get_vertex_data(path[i]).name; } std::cout << std::endl; } else { std::cout << "No such bus." << std::endl; } } void Dialog::query_path() { std::string a, b; std::cout << "Enter A and B:" << std::endl; std::cout << ">>> "; std::cin >> a >> b; VertexIndex ai, bi; if ((ai = map.find_vertex(a)) != -1 && (bi = map.find_vertex(b)) != -1) {