无权最短路径选择

图类的数据成员除了顶点的集合外还有一个记录起始顶点的数据成员。顶点的数据成员有距离起始顶点的最短距离，邻接表，最短路径上顶点的上一个顶点三个数据成员。首先将起始顶点入队，距离为零，然后将其出队，更新其邻接顶点的距离并把它们放入队列。重复到队列为空为止。

头文件

#include <vector> #include <climits> #include <iostream> class Graph { public: explicit Graph(int vertexNum):v(vertexNum+1) { for(auto x:v) { x.dist=INT_MAX; x.path=nullptr; x.adjacentList=std::vector<Vertex*>{}; } initialVertex=0; } void setVertex(int vertexIndex,const std::vector<int> & adjacentIndex) { //创建邻接表 for(auto x:adjacentIndex) { v[vertexIndex].adjacentList.push_back(&v[x]); } } void unweighted(int initialVer); void printPath(int end) { if(v[end].dist==INT_MAX) std::cout<<"V"<<end<<" can not be reached by V"<<initialVertex<<std::endl; else { std::cout<<"shortest length from V"<<initialVertex<<" to V" <<end<<" is "<<v[end].dist<<std::endl; printPath(&v[end]); std::cout<<std::endl; } } private: struct Vertex { int dist; //距离 std::vector<Vertex*> adjacentList; //邻接表 Vertex* path; //上一个节点 explicit Vertex(const std::vector<Vertex*> & adList=std::vector<Vertex*>{}) { dist=INT_MAX; path=nullptr; adjacentList=adList; } }; std::vector<Vertex> v; int initialVertex; void printPath(Vertex* ver); };

cpp文件

#include "Graph.hpp" #include <queue> void Graph::unweighted(int initialVer) { initialVertex=initialVer; v[initialVer].dist=0; std::queue<Vertex*> q; q.push(&v[initialVer]); while(!q.empty()) { auto ver=q.front(); q.pop(); for(int i=0;i<ver->adjacentList.size();++i) { //防止绕圈 if (ver->adjacentList[i]->dist==INT_MAX) { ver->adjacentList[i]->dist=ver->dist+1; ver->adjacentList[i]->path=ver; q.push(ver->adjacentList[i]); } } } } void Graph::printPath(Vertex* ver) { if(ver->path!=nullptr) { printPath(ver->path); std::cout<<" to "; } std::cout<<"V"<<ver-&v[0]; }

main.cpp

#include "Graph.hpp" #include <iostream> using namespace std; int main(int argc, const char * argv[]) { //图由顶点和边组成 Graph g(7);//顶点数 //输入各个顶点的边（邻接顶点） g.setVertex(1, vector<int>{2,4}); g.setVertex(2, vector<int>{4,5}); g.setVertex(3, vector<int>{1,6}); g.setVertex(4, vector<int>{3,5,6,7}); g.setVertex(5, vector<int>{7}); g.setVertex(6, vector<int>{}); g.setVertex(7, vector<int>{6}); g.unweighted(3); for(int i=1;i<=7;++i) { g.printPath(i); cout<<endl; } cout<<endl; return 0; }

结果

shortest length from V3 to V1 is 1 V3 to V1

shortest length from V3 to V2 is 2 V3 to V1 to V2

shortest length from V3 to V3 is 0 V3

shortest length from V3 to V4 is 2 V3 to V1 to V4

shortest length from V3 to V5 is 3 V3 to V1 to V2 to V5

shortest length from V3 to V6 is 1 V3 to V6

shortest length from V3 to V7 is 3 V3 to V1 to V4 to V7