求两点之间的所有路径(广度优先与回溯法结合)

#include <iostream> #include < vector > #include <climits> using namespace std; vector<vector<int>> search( unsigned,unsigned ); bool Circle(int,vector<int>); int main() { vector<vector<int>> AllPath; unsigned v0,v1; cin>>v0>>v1; AllPath=search(v0,v1); cout<<"--------------"; cout<<"AllPath:"<<endl; for(unsigned i=0;i<AllPath.size();++i) {for(unsigned k=0;k<AllPath[i].size();++k) cout<<AllPath[i][k]; cout<<endl;} cout<<"---------------"; return 0; } vector<vector<int>> search(unsigned v0,unsigned v1) { int Adj[6][6]={ {1,1,1,1,1,1}, {1,1,1,1,1,1}, {1,1,1,1,1,1}, {1,1,1,1,1,1}, {1,1,1,1,1,1}, {1,1,1,1,1,1} }; vector<int> temp; vector<vector<int>> ADL;//邻接表 unsigned num=6; unsigned i,k,j; for(i=0;i<num;++i) { for(j=0;j<num;++j) { if(Adj[i][j]!=INT_MAX && Adj[i][j]!=0) temp.push_back(j); } ADL.push_back(temp); temp.clear(); } vector<vector<int>> AllPath; vector<int> path; vector<vector<int>> stack; //创建临时的二维栈 path.push_back(v0); stack.push_back(path); stack.push_back(ADL[v0]); while( stack.size() !=1 ) { int pop=stack[stack.size()-1].back(); path.push_back(pop); if(Circle(pop,path)) { path.pop_back(); stack[stack.size()-1].pop_back(); } else if( pop == v1 ) { AllPath.push_back(path); path.pop_back(); stack[stack.size()-1].pop_back(); } else { stack.push_back(ADL[pop]); } while(stack[stack.size()-1].size()==0&&stack.size() !=1) { stack.pop_back(); stack[stack.size()-1].pop_back(); path.pop_back(); } } return AllPath; } bool Circle(int pop,vector<int> path) { for(unsigned i=0;i<path.size()-1;++i) if(pop==path[i]) return true; return false; }