本文共 4833 字，大约阅读时间需要 16 分钟。
邻接表:
dfs4(a,start,end,visited,stack,-1)//递归
dfs5(a,start,end);//非递归
邻接矩阵:(可以直接用矩阵数据计算路径长度)
dfs6(m,start,end,visited,stack,-1);//递归
dfs7(m,start,end);//非递归
递归的思路来自https://blog.csdn.net/hackersuye/article/details/79044555
非递归是自己做的
大家可以试试。
邻接表和邻接矩阵的写法是来自《天勤高分笔记数据结构》。
邻接表
package dfs;class AGraph{ int n; int e=0; VNode adjlist[]; public AGraph(int n) { super(); this.n = n; adjlist=new VNode[n]; } }package dfs;class ArcNode{ int adjvex; ArcNode nextarc; int weight;//weight就是adjlist[i]->adjvex的权重 //对应于邻接矩阵的权重m[i][adjvex] AGraph a;//记录边数时，需要图a int edge_type=0;//初始化为回边(P99.8) public ArcNode(int adjvex, AGraph a) { super(); this.adjvex = adjvex; this.a = a; a.e+=1; } public ArcNode() { } public ArcNode (int adjvex){ this.adjvex=adjvex; }; }package dfs;class VNode{ //邻接矩阵的顶点也可以用这个 ArcNode firstarc; char info; int level;//对应于99.8，对每个点，都要有层级 public VNode(char info) { this.info = info; } int ini=1;//用于利用邻接表非递归输出全部路径的DFS //在该次应该指向链接表的哪一个arc //初始值为1,即firstarc;若大于1，不停地取nextarc， //直到找到对应的 第ini边 }邻接矩阵
package dfs;public class VertexType { int no;int ini=0;//用于利用邻接矩阵非递归输出全部路径的DFS//这里的ini是指向的顶点数字（因为用邻接矩阵总要从后向前遍历）//不是VNode里面的第几个}package dfs;public class MGraph { int n;int e=0;//n为顶点数，e为边数//int edges[][];VertexType vex[];int edges[][]; public MGraph(int n) { this.n = n; edges=new int[n][n]; vex=new VertexType[n]; for(int i=0;i<vex.length;i++) vex[i]=new VertexType(); }public void set(int i,int j){ edges[i][j]=1; //如果是无向图的话 edges[j][i]=1; e+=2;} }4个方法
public static void dfs4(AGraph a,int start,int end, int visited[],int stack[],int top) { visited[start]=1; stack[++top]=start; if(start==end) { System.out.println("成功"); for(int i=0;i<=top;i++) System.out.print(stack[i]+" "); System.out.println("");//出栈 top--; visited[end]=0; //visited[stack[top]]=0;top--; return; } ArcNode arc=a.adjlist[start].firstarc; while(arc!=null) { if(visited[arc.adjvex]==0) dfs4(a,arc.adjvex,end,visited,stack,top); arc=arc.nextarc; } if(arc==null) { top--;visited[start]=0; //visited[stack[top]]=0;top--; } } public static void dfs5(AGraph a,int start,int end) { //每次进栈一个元素或出栈一个元素 int visited[]=new int[a.n];//初始化为0 int stack[]=new int[a.n]; int top=-1; stack[++top]=start;//stack存放的是adjlist中某一个的位置 visited[start]=1; while(top!=-1) { ArcNode arc=null; int x=stack[top]; //在if else下面统一出栈，设定为未访问 if(x==end) //栈输出 //9在这里是终点 { System.out.println("成功"); for(int i=0;i<=top;i++) System.out.print(stack[i]+" "); System.out.println(""); } else//m是指明arc是x指向的第几个顶点//这个顶点必须满足://①未被访问//②m必须大于等于ini(小于ini的都已经出栈或不行了，不用考虑) { arc=a.adjlist[x].firstarc; int m=1; while(arc!=null) { if(visited[arc.adjvex]==0&&m>=a.adjlist[x].ini) { stack[++top]=arc.adjvex; visited[arc.adjvex]=1;break;} else { arc=arc.nextarc;m++;}} } if(arc==null)//此处逻辑为先出栈，出栈的元素指向的边还原为firstarc//出栈的元素b一定是出栈后栈顶元素a指向的某一个顶点//我们找到b是a的第m个顶点，把a的ini设置为m+1//使其不要重复搜索前m个//(前面的做法一定是按顺序的，说明前m个已经搜过) { int y=stack[top--];//出栈 visited[y]=0; a.adjlist[y].ini=1; if(top>=0) { ArcNode ar=a.adjlist[stack[top]].firstarc; int count=1; //由上面，我们知道进栈的一定>=ini //所以首先ar要变成ini while(count<a.adjlist[stack[top]].ini) { ar=ar.nextarc; count++;} //再往下找 int number=ar.adjvex; while(number!=y) { a.adjlist[stack[top]].ini++; ar=ar.nextarc; number=ar.adjvex; } a.adjlist[stack[top]].ini++; } } } } public static void dfs6(MGraph m,int start,int end, int visited[],int stack[],int top) { visited[start]=1; stack[++top]=start; if(start==end) { System.out.println("成功"); for(int i=0;i<=top;i++) System.out.print(stack[i]+" "); System.out.println("");//出栈 top--; visited[end]=0; //visited[stack[top]]=0;top--; return; } for(int i=0;i<m.n;i++) if(m.edges[start][i]==1&&visited[i]==0) { dfs6(m,i,end,visited,stack,top); } top--; visited[start]=0; } public static void dfs7(MGraph m,int start,int end) { //每次进栈一个元素或出栈一个元素 int visited[]=new int[m.n];//初始化为0 int stack[]=new int[m.n]; int top=-1; stack[++top]=start;//stack存放的是vex中某一个的位置 visited[start]=1; while(top!=-1) { int x=stack[top]; int ii=m.n;//ii为条件 //在if以及else下面统一出栈 if(x==end) //栈输出 { System.out.println("成功"); for(int i=0;i<=top;i++) System.out.print(stack[i]+" "); System.out.println(""); } else//m是指明arc是x指向的第几个顶点//这个顶点必须满足://①未被访问//②ii必须大于等于x的ini(小于ini的都已经出栈或不行了，不用考虑)//③ii必须与x有边 { for(ii=m.vex[x].ini;ii<m.n;ii++) if(visited[ii]==0&&m.edges[x][ii]!=0) { stack[++top]=ii; visited[ii]=1;break;} } if(ii==m.n)//此处逻辑为先出栈，出栈的元素指向的边还原为0//出栈的元素y一定是出栈后栈顶元素a指向的某一个顶点//把a的ini设置为y+1//使其不要重复搜索前y个顶点//(前面的做法一定是按顺序的，说明前y个已经搜过或者根本不满足条件) { int y=stack[top--];//出栈 visited[y]=0; m.vex[y].ini=0; if(top>=0) m.vex[stack[top]].ini=y+1; } } }