mysileng

求两定点之间的全部路径，其根本是一个涉及到搜索和回溯的问题。我们设计算法时所关心的首要问题是：按照何种顺序搜索和回溯才能保证路径可以不重不漏地被全部找到。
 

图的存储结构：邻接矩阵。Arcs

工作结构：结点栈 mystack;

状态保存结构： 

（1） VertexStatus[]={0,0,0,1,1,…}。当结点未进栈或者已经出栈，则其对应的状态为0，否则状态为1；

（2） ArcStatus[][]={0,0,1,0,1…..}当且仅当边的两个结点都在栈外时，边的状态才为0，否则为1。

注意我们只所以设计如上结点、边两个状态存储结构，就是依据于path的定义，结点不重复，边不重复。具有边状态存储结构，也是我的算法与其他算法根本上的不同。

不失一般性，我们假设原点的编号最小为0,目标点的编号最大N。我们的问题转换成了，求最小编号的节点与最大编号的节点之间的所有路径。

Paths={}//路径集合

VertexStatus[]={0};//全部置0

ArcStatus[][]={0};////全部置0

mystack.push(0);

VertexStatus[0]=1;

While(!mystack.empty()){

  Int elem= mystack.top();//获得栈顶元素

  if(elem==N){//找到了一条路径

path=Traverse(mystack);

Paths.add(path);

VertexStatus[elem]=0;

UpdateArcStatus();//更新ArcStatus[][]，使得所有两个端点都不在栈内的边的状态为0

mystack.pop();//移除栈顶元素
  }else{

i=0;
          For(;i<N;i++){ 
      if(VertexStatus[i]=0&&ArcStatus[elem][i]=0&&Arcs.contain(elem,i)){

VertexStatus[i]=1;

ArcStatus[elem][i]=1;

Mystack.push(i);//入栈
    break;
  }
}
if(i=N){//该节点没有符合要求的后续节点

VertexStatus[elem]=0;

    UpdateArcStaus();////更新ArcStatus[][]，使得所有两个端点都不在栈内的边的状为0

          Mystack.pop();//出栈
    }
   }
}