mysileng

求兩定點之間的全部路徑，其根本是一個涉及到搜索和回溯的問題。我們設計算法時所關心的首要問題是：按照何種順序搜索和回溯才能保證路徑可以不重不漏地被全部找到。
 

圖的存儲結構：鄰接矩陣。Arcs

工作結構：結點棧 mystack;

狀態(tài)保存結構： 

（1） VertexStatus[]={0,0,0,1,1,…}。當結點未進棧或者已經(jīng)出棧，則其對應的狀態(tài)為0，否則狀態(tài)為1；

（2） ArcStatus[][]={0,0,1,0,1…..}當且僅當邊的兩個結點都在棧外時，邊的狀態(tài)才為0，否則為1。

注意我們只所以設計如上結點、邊兩個狀態(tài)存儲結構，就是依據(jù)于path的定義，結點不重復，邊不重復。具有邊狀態(tài)存儲結構，也是我的算法與其他算法根本上的不同。

不失一般性，我們假設原點的編號最小為0,目標點的編號最大N。我們的問題轉換成了，求最小編號的節(jié)點與最大編號的節(jié)點之間的所有路徑。

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[][]，使得所有兩個端點都不在棧內的邊的狀態(tài)為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){//該節(jié)點沒有符合要求的后續(xù)節(jié)點

VertexStatus[elem]=0;

    UpdateArcStaus();////更新ArcStatus[][]，使得所有兩個端點都不在棧內的邊的狀為0

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