提取路径广度优先搜索BFS代码C++

/********************************************************* * Source file of BFS * Author: Lantao Liu **********************************************************/ #include "bfs.h" //generate random edges and wrapped with a vector vector<pair<int,int> > BFS::generate_edges(void){ vector<pair<int, int> > edges; edges.reserve(M); for(int i=0; i<M; i++){ int rand0 = random()%(N-1); int rand1; do{ rand1 = random()%N; }while(rand1 <= rand0); edges.push_back(pair<int, int>(rand0, rand1)); }//end for for(int i = 0; i< M; i++) cout << "("<<edges[i].first<<","<<edges[i].second<<") "; cout<<endl; return edges; } //find the shorted path and return the length. int BFS::shortest_path(const vector<pair<int, int> > edges){ deque<int> q; int shortest; //__gnu_cxx::hash_map<int, int> hm; //typedef __gnu_cxx::hash_map<int, int>::value_type hs; for(unsigned int i =0; i < edges.size(); i++) if(edges[i].first == 0){ q.push_back(edges[i].first); break;} if(!q.size()){ cerr<<"Unreachable!!"<<endl; reachable = false; return 0; } paths.clear(); // paths.reserve(N); paths.resize(N); //todo: why do I need to resize here? paths[0].first=0; paths[0].second.push_back(0); while(q.size()){ int front = q.front(); for(unsigned int j=0; j< edges.size(); j++){ if(edges[j].first == front){ q.push_back(edges[j].second); //hm.erase(edges[j].first); //hm.insert(hs(edges[j].first, edges[j].second)); if(color[edges[j].second] == "white") { int length = paths[front].first; vector<int> path = paths[front].second; path.push_back(edges[j].second); length ++; paths[edges[j].second] = pair<int, vector<int> >(length, path); color[edges[j].second] = "grey"; } else{ if(paths[front].first < paths[edges[j].second].first -1){ paths[edges[j].second].first=paths[front].first + 1; paths[edges[j].second].second.clear(); paths[edges[j].second].second = paths[front].second; paths[edges[j].second].second.push_back(edges[j].second);} } } if(front == N-1 ){ cout<<"Shortest path found: "<<endl; for(unsigned int j=0; j<paths[N-1].second.size(); j++) cout<<paths[N-1].second[j]<<" "; cout<<endl; shortest = paths[N-1].second.size(); return shortest; } } //end for q.pop_front(); if(!q.size()){ cout<<"Unreachable!!"<<endl; reachable =false; return 0; } } //end while } //find the longest path and return the length int BFS::longest_path(const vector<pair<int, int> > edges){ deque<int> q; int longest; //__gnu_cxx::hash_map<int, int> hm; //typedef __gnu_cxx::hash_map<int, int>::value_type hs; for(unsigned int i =0; i < edges.size(); i++) if(edges[i].first == 0){ q.push_back(edges[i].first); break;} if(!q.size()){ cerr<<"Unreachable!!!"<<endl; reachable = false; } if(!reachable) return 0; paths[0].first=0; paths[0].second.push_back(0); while(q.size()){ int front = q.front(); for(unsigned int j=0; j< edges.size(); j++){ if(edges[j].first == front){ q.push_back(edges[j].second); //hm.erase(edges[j].first); //hm.insert(hs(edges[j].first, edges[j].second)); if(color[edges[j].second] == "white") { int length = paths[front].first; vector<int> path = paths[front].second; path.push_back(edges[j].second); length ++; paths[edges[j].second] = pair<int, vector<int> >(length, path); color[edges[j].second] = "grey"; } else{ if(paths[front].first >= paths[edges[j].second].first){ paths[edges[j].second].first=paths[front].first + 1; paths[edges[j].second].second.clear(); paths[edges[j].second].second = paths[front].second; paths[edges[j].second].second.push_back(edges[j].second);} } } } //end for q.pop_front(); } //end while if(reachable){ cout<<"Longest path found: "<<endl; for(unsigned int j=0; j<paths[N-1].second.size(); j++) cout<<paths[N-1].second[j]<<" "; cout<<endl; longest = paths[N-1].second.size(); } return longest; } int main(int argc, char** argv) { if(argc<3) cout<<"Usage: ./exe N M tries"<<endl; int n, m, t; n = atoi(argv[1]); m = atoi(argv[2]); t = atoi(argv[3]); cout << "The parameters you have entered: "<< endl <<"Vertices number: "<<n <<endl <<"Edges number: " <<m <<endl <<"Tries number: " <<t << endl; double shortest_stat =0, average_shortest=0; double longest_stat = 0, average_longest =0; for(int i=0; i<t; i++) { cout<<"=================================="<<endl; cout<<"The "<<i<<"th attempts: "<<endl; vector< pair<int, int> > edges; edges.reserve(m); BFS bfs(n, m, t); edges = bfs.generate_edges(); shortest_stat += bfs.shortest_path(edges); longest_stat += bfs.longest_path(edges); cout<<endl<<endl; } average_shortest= shortest_stat/t; average_longest =longest_stat /t; cout<<"nstates = "<<n<<", nedges = "<<m<<endl;//, reachable=3/5=0.60 cout<<"avg len of shortest path: "<<average_shortest<<endl; //, stdev=0.47 cout<<"avg len of longest path: "<<average_longest<<endl; //, stdev=0.47 return 0; }