本文共 3121 字，大约阅读时间需要 10 分钟。

邻接表:

邻接矩阵:(可以直接用矩阵数据计算路径长度)

递归的思路来自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

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
   
    =0)				m.vex[stack[top]].ini=y+1;		   		}      }	}