DFS算法：遍历任意两点之间的所有路径并输出.docVIP

DFS算法：遍历任意两点之间的所有路径并输出 代码大部分都是从数据结构书上来的，水平有限仅供参考！希望对课程设计要用到这个算法的同学有帮助 先看运行结果： 起点1，终点7 基本代码都是从数据结构书上抄来的，重点看红字。 全部源代码 //mian的实现 #include stdafx.h #include iostream #include assert.h #include graph.h #include Graphm.h #include AList.h using namespace std; void PrintPath(AListint* path){ //打印路径 int L=path-Length(); int temp=-1; for(int i=0;iL;i++) { path-setPos(i); path-getValue(temp); couttemp; if(i!=L-1) cout; } coutendl; } void DFS(Graph* G,int v,int end,AListint* path){ G-setMark(v,VISITED); //标记为已访问，防止路径重复 path-append(v); //记录节点 if(v==end) //到达终点 //在这里对路径进行处理 PrintPath(path); //打印整条路径 else //否则 for(int w=G-first(v);wG-n();w=G-next(v,w)) //继续寻找下一个未访问的点 if(G-getMark(w)==UNVISITED) DFS(G,w,end,path);//把找到的未访问节点w作为起点，进入递归 //重点：没有未访问邻居节点（陷入了死路）或者到达终点,后退找新的未访问路径 G-setMark(v,UNVISITED); //回溯 标记为未访问 //从path中移除V path-setEnd(); path-remove(); } int main(int argc, char* argv[]) { int mapTemp[8][8]={ {0,1,1,0,0,0,0,0},//0 {1,0,0,1,1,0,0,0},//1 {1,0,0,1,0,1,0,0},//2 {0,1,1,0,1,1,0,0},//3 {0,1,0,1,0,0,1,1},//4 {0,0,1,1,0,0,1,0},//5 {0,0,0,0,1,1,0,0},//6 {0,0,0,0,1,0,0,0} //7 }; // 7 // / // 1--4 // /\ /\ // 0 3 6 // \/ \ / // 2--5 // //初始化 Graphm *map=new Graphm(8); for(int i=0;i8;i++) for(int j=0;j8;j++) map-setEdge(i,j,mapTemp[i][j]);//set edge(v1,v2)to wgt map-setAllMark(UNVISITED); AListint *path=new AListint; int s=1;//起点 int e=7;//终点 //开始遍历 DFS(map,s,e,path); return 0; } /**********************************************************************/ //图的抽象类 //Graph.h class Graph{ public: virtual n()=0; virtual e()=0; virtual int first(int)=0; virtual int next(int,int)=0; virtual void setEdge(int,int,in