求兩定點之間的全部路徑，其根本是一個涉及到搜索和回溯的問題。我們設(shè)計算法時所關(guān)心的首要問題是：按照何種順序搜索和回溯才能保證路徑可以不重不漏地被全部找到。
圖的存儲結(jié)構(gòu)：鄰接矩陣。Arcs
工作結(jié)構(gòu)：結(jié)點棧 mystack;
狀態(tài)保存結(jié)構(gòu)：
（1） VertexStatus[]={0,0,0,1,1,…}。當(dāng)結(jié)點未進(jìn)棧或者已經(jīng)出棧，則其對應(yīng)的狀態(tài)為0，否則狀態(tài)為1；
（2） ArcStatus[][]={0,0,1,0,1…..}當(dāng)且僅當(dāng)邊的兩個結(jié)點都在棧外時，邊的狀態(tài)才為0，否則為1。
注意我們只所以設(shè)計如上結(jié)點、邊兩個狀態(tài)存儲結(jié)構(gòu)，就是依據(jù)于path的定義，結(jié)點不重復(fù)，邊不重復(fù)。具有邊狀態(tài)存儲結(jié)構(gòu)，也是我的算法與其他算法根本上的不同。
不失一般性，我們假設(shè)原點的編號最小為0,目標(biāo)點的編號最大N。我們的問題轉(zhuǎ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[][]，使得所有兩個端點都不在棧內(nèi)的邊的狀態(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[][]，使得所有兩個端點都不在棧內(nèi)的邊的狀為0
Mystack.pop();//出棧
}
}
}