学校数据结构的课程实验之一。
用到的数据结构：无向带权图
用到的算法：Floyd最短路径算法，深度优先搜索（递归实现）
需求分析：
设计一个校园导航程序，为访客提供各种信息查询服务：
1. 以图中各顶点表示校内各单位地点，存放单位名称，代号，简介等信息；以边表示路径，存放路径长度等相关信息。
2. 图中任意单位地点相关信息的查询。
3. 图中任意单位的问路查询，即查询任意两个单位之间的一条最短的路径。
2. 从图中任意单位地点出发的一条深度优先遍历路径。
主函数：
1 #include <iostream> 2 #include "School.h" 3 using namespace std; 4 5 int main() 6 { 7 School mySchool=School("School.txt"); 8 char choice='y'; 9 while(choice=='y') 10 { 11 cout << "请选择操作"<<endl; 12 cout << "--------------------------------" << endl; 13 cout << "1----查看地点列表" << endl; 14 cout << "2----查看地点简介" << endl; 15 cout << "3----查询最短路径" << endl; 16 cout << "4----从一点出发遍历" << endl; 17 cout << "5----任意一点的可直达地点" << endl; 18 cout << "--------------------------------" << endl; 19 int option; 20 cin >> option; 21 switch (option) 22 { 23 case 1: mySchool.display(); break; 24 case 2: mySchool.search(); break; 25 case 3: mySchool.path(); break; 26 case 4: mySchool.traverse(); break; 27 case 5: mySchool.reachable(); break; 28 } 29 cout << "继续吗?[y/n]"; 30 cin >> choice; 31 } 32 return 0; 33 }
图类（邻接矩阵存储，因有向图是无向图的超集，所以可以定义为有向图，邻接矩阵为对称阵）
1 #include <fstream> 2 #include <string> 3 4 template <class Vertex,int graph_size> 5 class Digraph 6 { 7 public: 8 Digraph() 9 { 10 count=0; 11 for (int i = 0; i < graph_size; i++) 12 adjacency[i][i] = 0; 13 } 14 void insert(Vertex &new_entry) 15 { 16 nodes[count++]=new_entry; 17 } 18 void distance_set(int i, int j, int dis) 19 { 20 adjacency[i][j] = adjacency[j][i] = dis; 21 } 22 void traverse(void (*visit)(Vertex &))//遍历整个图（逐个访问各结点） 23 { 24 for(int i=0;i<graph_size;i++) 25 (*visit)(nodes[i]); 26 } 27 void search_vertex(int num,Vertex &target) 28 { 29 target=nodes[num]; 30 } 31 void calculate_path()//计算最短路径并将结果更新到以上两个二维数组里 32 { 33 for (int i = 0; i < graph_size; i++) 34 { 35 for (int j = 0; j < graph_size; j++) 36 {//初始化路径长度数组，结点跟踪数组 37 shortest_dis[i][j] = adjacency[i][j]; 38 trace_node[i][j] = j; 39 } 40 } 41 cout << "这是邻接矩阵：" << endl; 42 for (int i = 0; i < graph_size; i++) 43 { 44 for (int j = 0; j < graph_size; j++) 45 cout << adjacency[i][j] << " "; 46 cout << endl; 47 } 48 //Floyd算法计算任意两点之间的最短路径 49 for (int k = 0; k < graph_size; k++) 50 for (int v = 0; v < graph_size; v++) 51 for (int w = 0; w < graph_size; w++) 52 if (shortest_dis[v][k] + shortest_dis[k][w] < shortest_dis[v][w]) 53 { 54 shortest_dis[v][w] = shortest_dis[v][k] + shortest_dis[k][w]; 55 trace_node[v][w] = trace_node[v][k]; 56 } 57 cout << "这是最短路径数组：" << endl; 58 for (int i = 0; i < graph_size; i++) 59 { 60 for (int j = 0; j < graph_size; j++) 61 cout << shortest_dis[i][j] << " "; 62 cout << endl; 63 } 64 cout << "这是结点跟踪数组：" << endl; 65 for (int i = 0; i < graph_size; i++) 66 { 67 for (int j = 0; j < graph_size; j++) 68 cout << trace_node[i][j] << " "; 69 cout << endl; 70 } 71 } 72 void shortest_path(int i, int j) 73 { 74 cout << "从" << i << "到" << j << "的最短路径长度为" << shortest_dis[i][j] << endl; 75 cout << "路径为：" << endl; 76 int k = trace_node[i][j]; 77 cout << i ; 78 while (k != j) 79 { 80 cout << "->" << k; 81 k = trace_node[k][j];//从起点出发，找到途经结点 82 } 83 cout << "->" << j << endl; 84 } 85 void connected(int v)//输出所有和v直达的结点 86 { 87 for (int i = 0; i < graph_size; i++) 88 { 89 if (adjacency[v][i] != 100 && adjacency[v][i] != 0) 90 cout << nodes[i] << " 距离为：" << adjacency[v][i] << ";" << endl; 91 } 92 } 93 int BFS(int v,void (*visit)(Vertex &)) 94 { 95 distance = 0; 96 bool visited[graph_size] = { false }; 97 Vertex src = nodes[v];//找到选定的源点 98 visited[v] = true; 99 (*visit)(src); 100 for (int i = 0; i < graph_size; i++) 101 { 102 if (adjacency[v][i] != 100 && adjacency[v][i] != 0)//对相邻点进行深度优先遍历 103 traverse(i, visited, visit); 104 } 105 return distance; 106 } 107 private: 108 int count;//结点数 109 int distance;//一条遍历路径总长 110 int adjacency[graph_size][graph_size];//存储权的邻接矩阵 111 Vertex nodes[graph_size];//存储结点内容的一维数组 112 int shortest_dis[graph_size][graph_size];//保存最短路径长度 113 int trace_node[graph_size][graph_size];//保存结点跟踪路径 114 void traverse(int v, bool visited[], void (*visit)(Vertex &))//辅助遍历函数 115 { 116 if (visited[v] == false) 117 { 118 (*visit)(nodes[v]); 119 visited[v] = true; 120 for (int i = 0; i < graph_size; i++) 121 if (adjacency[v][i] != 100 && adjacency[v][i] != 0 && visited[i] == false) 122 { 123 traverse(i, visited, visit);//递归地进行深度优先遍历 124 distance += adjacency[v][i]; 125 } 126 127 } 128 } 129 };
学校类
1 #include <fstream> 2 #include <string> 3 #include "Digraph.h" 4 using namespace std; 5 6 struct Place//地点定义 7 { 8 int number; 9 string name; 10 string introduction; 11 12 Place(){} 13 Place(int num,string nam,string intro):number(num),name(nam),introduction(intro){} 14 void print()//显示此地点的信息 15 { 16 cout<<"---------------------------"<<endl; 17 cout<<"编号："<<number<<endl; 18 cout<<"地点名："<<name<<endl; 19 cout<<"简介："<<introduction<<endl; 20 cout<<"---------------------------"<<endl; 21 } 22 }; 23 ostream& operator<<(ostream &os, Place &aPlace)//重载输出运算符 24 { 25 os << aPlace.number << ":" << aPlace.name; 26 return os; 27 } 28 ofstream outFile;//输出流 29 30 class School 31 { 32 private: 33 int total;//总的地点数 34 Digraph<Place,13> places_graph; 35 void readFile(const char filename[20])//读文件 36 { 37 total = 0; 38 ifstream inFile; 39 inFile.open(filename); 40 char trying; 41 while(inFile.is_open() && !inFile.eof()) 42 { 43 //先试探是否为结束符 44 inFile >> trying; 45 if (trying == '#') break; 46 else 47 { 48 inFile.putback(trying); 49 int number; 50 inFile>>number; 51 string name; 52 inFile>>name; 53 string introduction; 54 inFile>>introduction; 55 Place aPlace=Place(number,name,introduction); 56 //aPlace.print();//显示这个地点的信息 57 places_graph.insert(aPlace); 58 total++; 59 } 60 } 61 for (int i = 0; i < 13; i++)//读入距离内容 62 for (int j = 0; j < 13; j++) 63 { 64 int dis; 65 inFile >> dis; 66 places_graph.distance_set(i, j, dis); 67 } 68 inFile.close(); 69 places_graph.calculate_path();//计算所有最短路径并存入数组 70 cout << "学校共有" << total << "个地方"<<endl; 71 } 72 static void readPlace(Place &aPlace) 73 { 74 outFile<<aPlace.number<<endl; 75 outFile<<aPlace.name<<endl; 76 outFile<<aPlace.introduction<<endl; 77 } 78 static void print(Place &aPlace)//显示此地点的信息编号、名称 79 { 80 cout<<aPlace.number<<": "<<aPlace.name<<endl; 81 } 82 static void visit(Place &aPlace) 83 { 84 cout << "->" << aPlace.number << ":" << aPlace.name << endl; 85 } 86 public: 87 School(const char filename[20]) 88 { 89 readFile(filename); 90 } 91 void display() 92 { 93 cout<<"以下为学校的所有地点："<<endl; 94 places_graph.traverse(print); 95 } 96 void search() 97 { 98 cout<<"请输入要查询的地点编号："; 99 int num; 100 cin>>num; 101 Place aPlace; 102 places_graph.search_vertex(num,aPlace);//查到要查的地点 103 cout<<"以下是这一地点的信息："<<endl; 104 aPlace.print(); 105 } 106 void path() 107 { 108 cout << "请输入想查询最短路径的两个地点的编号（如：5 7）："; 109 int i, j; 110 cin >> i >> j; 111 places_graph.shortest_path(i, j); 112 } 113 void traverse()//深度优先遍历，输出路线 114 { 115 cout << "请输入源点的编号："; 116 int v; 117 cin >> v; 118 int distance; 119 distance = places_graph.BFS(v, visit); 120 cout << endl << "路径总长为：" << distance<<endl; 121 } 122 void reachable() 123 { 124 cout << "请输入源点的编号："; 125 int v; 126 cin >> v; 127 cout << "和地点" << v << "有直达路径的地点如下：" << endl; 128 places_graph.connected(v); 129 } 130 };
主函数流程图：
运行截图：
附：测试用的文件School.txt内容
0 前门 南门；车辆进出 1 教一楼 阶梯教室；英语教室 2 教二楼 普通教室 3 教三楼 实验室；办公室；阶梯教室 4 学一公寓 男生宿舍 5 学二公寓 男生宿舍 6 学三公寓 女生宿舍 7 学四公寓 男生宿舍 8 食堂 一层；二层；清真 9 水房 在食堂旁边 10 操场 300米一圈的跑道 11 图书馆 借阅部；自习室 12 后门 北门；取快递 # 0 1 4 8 6 100 100 10 100 1 100 10 100 1 0 3 4 5 100 10 100 1 100 1 100 100 4 3 0 10 1 7 100 6 100 10 100 100 8 8 4 10 0 2 100 3 100 100 6 5 9 7 6 5 1 2 0 3 6 9 100 7 9 8 5 100 100 7 100 3 0 100 5 100 6 7 8 4 100 10 100 3 6 100 0 2 7 2 9 10 2 10 100 6 100 9 5 2 0 4 100 2 3 7 100 1 100 100 100 100 7 4 0 10 4 5 1 1 100 10 6 7 6 2 100 10 0 8 5 7 100 1 100 5 9 7 9 2 4 8 0 2 9 10 100 100 9 8 8 10 3 5 5 2 0 100 100 100 8 7 5 4 2 7 1 7 9 100 0