用无向带权图实现校园导航系统-白红宇

学校数据结构的课程实验之一。

用到的数据结构：无向带权图

用到的算法：Floyd最短路径算法，深度优先搜索（递归实现）

需求分析：

　　设计一个校园导航程序，为访客提供各种信息查询服务：

1. 以图中各顶点表示校内各单位地点，存放单位名称，代号，简介等信息；以边表示路径，存放路径长度等相关信息。

2. 图中任意单位地点相关信息的查询。

3. 图中任意单位的问路查询，即查询任意两个单位之间的一条最短的路径。

2. 从图中任意单位地点出发的一条深度优先遍历路径。

主函数：

1 #include 
     
       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 << "请选择操作"<
      
       > 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 
      
         2 #include 
       
          3   4 template 
        
           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
         
          " << 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 };

Digraph.h

学校类

1 #include 
     
        2 #include 
      
         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<<"---------------------------"<
       
         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 << "个地方"<
        
         " << 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<<"以下为学校的所有地点："<
         
          >num;101         Place aPlace;102         places_graph.search_vertex(num,aPlace);//查到要查的地点103         cout<<"以下是这一地点的信息："<
          
           > 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<
           
            > 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   5100 100   7 100   3   0 100   5 100   6   7   8   4100  10 100   3   6 100   0   2   7   2   9  10   210  100   6 100   9   5   2   0   4 100   2   3   7100   1 100 100 100 100   7   4   0  10   4   5   11   100  10   6   7   6   2 100  10   0   8   5   7100   1 100   5   9   7   9   2   4   8   0   2   910  100 100   9   8   8   10  3   5   5   2   0 100100 100   8   7   5   4   2   7   1   7   9  100  0

School.txt