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

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(AList* path){ //打印路径 int L=path->Length(); int temp=-1; for(int i=0;isetPos(i); path->getValue(temp); cout<>\"; } cout<void DFS(Graph* G,int v,int end,AList* path){ G->setMark(v,VISITED); //标记为已访问，防止路径重复 path->append(v); //记录节点

if(v==end) //到达终点 //在这里对路径进行处理 PrintPath(path); //打印整条路径 else //否则 for(int w=G->first(v);wn();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;i<8;i++) for(int j=0;j<8;j++) map->setEdge(i,j,mapTemp[i][j]);//set edge(v1,v2)to wgt map->setAllMark(UNVISITED); AList *path=new AList; 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,int)=0; virtual void delEdge(int,int)=0; virtual int weight(int,int)=0; virtual int getMark(int)=0; virtual void setMark(int,int)=0; virtual void setAllMark(int)=0; //自己添加的 };

/**********************************************************************/

//图的实现

//Graphm.h

#define UNVISITED 0 #define VISITED 1

class Graphm:public Graph{ //Implement adjacency mnatrix private: int numVertex,numEdge; int **matrix; //Pointer to adjacency matrix int *mark; //Pointer to mark array public: Graphm(int numVert){ //Mark graph w/numVert vertices int i,j; numVertex=numVert; numEdge=0; mark=new int[numVert]; //Initialize mark array for(i=0;iint i; for(i=v2+1;i//set edge(v1,v2)to wgt void setEdge(int v1,int v2,int wgt){ assert(wgt>=0); if(matrix[v1][v2]==0) numEdge++; matrix[v1][v2]=wgt; } void delEdge(int v1,int v2){ if(matrix[v1][v2]!=0) numEdge--; matrix[v1][v2]=0; } int weight(int v1,int v2){return matrix[v1][v2];} int getMark(int v){return mark[v];} void setMark(int v,int val){mark[v]=val;} void setAllMark(int val){ for(int i=0;i/**********************************************************************/ //用到的Alist

//AList.h

#ifndef _ALIST_H #define _ALIST_H

#ifndef NULL

const int NULL=0; #endif //NULL

template class AList{ private: int maxSize; int listSize;

int fence; Elem* listArray; void capacityExpansion() { Elem* temp=new Elem[maxSize*=2]; int n=listSize; Elem* destprt=temp; Elem* srcprt=listArray; while(n--) *destprt++=*srcprt++; delete[] listArray; listArray=temp; } public: AList(int sz=50){ maxSize=sz; listSize=fence=0; listArray=new Elem[maxSize]; } AList(AList &item){ maxSize=item.maxSize; listSize=item.listSize; fence=item.fence; listArray=new Elem[maxSize]; int n=listSize; Elem* destprt=listArray; Elem* srcoprt=item.listArray; while(n--) *destprt++=*srcprt++; } ~AList(){ delete []listArray; } void clear(){ //清除数组里的内容（maxSize->50） delete []listArray; listArray=new Elem[50]; listSize=fence=0; } void insert(Elem& item){ //在fence位置插入元素 if(listSize==maxSize)

capacityExpansion(); int n=rightLength(),i=listSize++; while(n--) listArray[i--]=listArray[i-1]; listArray[fence]=item; } void append(Elem& item){ //在数组末尾插入元素 if(listSize==maxSize) capacityExpansion(); listArray[listSize++]=item; }

void remove(Elem& item){ //删除fence位置的元素，通过引用返回被删元素

item=listArray[fence]; Elem* temp=new Elem[maxSize]; for(int i=0,j=0;ifence=listSize; } bool prev(){ //fence向前移动一位 (0=0) fence--; else return false; return true; } bool next(){ //fence向后移动一位(fence<=listSize) if(fence=0&&pos<=listSize) fence=pos; else return false; return true; } bool getValue(Elem& item){ // 获取fence所指元素 if(fence//后期修改的 int Length(){ return listSize; }

};

#endif //_ALIST_H