题目：

代码：

#include
    
           #include
     
         using namespace std;    void print(vector
      
        &path,int& number){//打印一条路径	cout<<"路径"<
       
        <<":";	for(vector
        
         ::iterator iter=path.begin();iter!=path.end();iter++)		cout<<*iter<<"-";}void FindPaths(int **p,int dim,int&pathNumber,vector
         
          & path,bool* citylabel,int currentcity,int dest) { if(currentcity==dest)//当前城市为终点城市 {pathNumber++; print(path,pathNumber); cout<
          
           <

nextcity; for(int j=0;j

::iterator it=nextcity.begin();it!=nextcity.end();it++) FindPaths(p,dim,pathNumber,path,citylabel,*it,dest); path.pop_back(); } citylabel[currentcity]=false;//标志当前城市已经存在搜索路径中(已经使用) } } int main() { int dim,start,dest;//分别代表城市总数，起点城市，终点城市 int pathNumber=0;//路径总数 vector

path; cin>>dim>>start>>dest; bool *citylabel=new bool[dim];//某个城市是否已经在搜索路径中使用 int **p=new int*[dim];//城市两两之间是否有路到达 vector

nextcity;//可能的下一个城市 for(int i=0;i

>p[i][j]; if(i==start&&p[i][j]==1&&j!=start)//可能的第2个城市 nextcity.push_back(j);} } citylabel[0]=true;//起点设置为已存在于搜索路径中，即已经使用 path.push_back(start); for(vector

::iterator it=nextcity.begin();it!=nextcity.end();it++)//以可能的第2个城市为基准，遍历 FindPaths(p,dim,pathNumber,path,citylabel,*it,dest); cout<<"路径总数为"<

当输入为：

6 1 5              1 0 0 0 1 0              1 1 1 1 0 0              0 0 1 0 1 1              0 0 1 1 0 1              0 0 0 1 1 1              0 0 0 0 0 1

输出为：路径总数为

即下列9种情况：

      1 0 4 3 2 5      1 0 4 3 5      1 0 4 5      1 2 4 3 5      1 2 4 5      1 2 5      1 3 2 5      1 3 2 4 5      1 3 5

思想：

1.简单的递归。设某个城市为当前城市，搜索其所有有路相连的下个城市，并存储至vector中。将当前城市设定为已经使用，遍历vector中存储的下一个城市，此时递归。一旦某个城市的所有可能的下一步方向遍历完，则将该城市设置为未在搜索路径中。

2.注意递归终止条件的设定。

转载于:https://www.cnblogs.com/engineerLF/p/5393124.html