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

众所周知，DFS可以用递归实现，也可以用栈来实现。某算法书上用递归实现，说顶点顺序的种类有两种，我又用栈实现，顶点的顺序又多了两种。不同的顶点顺序可以适应不同场合。

邻接表

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;	}	package dfs;class VNode{   //邻接矩阵的顶点也可以用这个	ArcNode firstarc;	char info;	int level;//对应于99.8，对每个点，都要有层级		public VNode(char info) {   				this.info = info;	}		}

栈实现(这里的两种顺序是进栈顺序和出栈顺序，这两种和下面递归的进栈顺序和出栈顺序不一样)：

public static void dfs1(AGraph a,int start,int visited[])//用栈和邻接表	{   	//-1表示未访问，-2表示是起始节点（前面没东西）		//这样才不会与数组index冲突		int stack[]=new int[a.n];		int top=-1;		stack[++top]=start;		visited[start]=-2;				while(top!=-1)		{   			int x=stack[top--];			ArcNode arc=a.adjlist[x].firstarc;			while(arc!=null)			{   					if(visited[arc.adjvex]==-1)				{   stack[++top]=arc.adjvex;				visited[arc.adjvex]=x;}							    arc=arc.nextarc;			}		}		/*如果我们要输出一条路径可以这样		 * 假设start为起点，x是终点		 * 		 * 		 * 在while(top!=-1)		 * 里面加上，找到x就break;		 * 		 * 		 * 		 * if(top!=-1)		 * {			 * while(x!=-2)			 * {			 * System.out.println(x);			 * x=visited[x];			 *}		 * }		 * 		 * else    没有路径		 * 		 * 		 *这样输出是倒序的，可以用一个栈储存然后正过来		 *或者用递归		 */			}public static void DFS1(AGraph a){   	//-1表示未访问，-2表示是起始节点（前面没东西）	int visited[]=new int[a.n];	for(int i=0;i

递归实现：

public static void dfs3(AGraph a,int start,int visited[],int before)	{   	visited[start]=before;	//进栈操作(按照课本上那种进栈顺序)	ArcNode arc=a.adjlist[start].firstarc;	while(arc!=null)	{   	if(visited[arc.adjvex]==-1)		{   dfs3(a,arc.adjvex,visited,start);}		arc=arc.nextarc;	}	//出栈操作(按照课本上出栈顺序)	}public static void DFS3(AGraph a){   	//-1表示未访问，-2表示是起始节点（前面没东西）	int visited[]=new int[a.n];	for(int i=0;i