DFS采用栈实现非递归

DFS核心类：

package com.dfs; import java.util.Stack; /** * 图的DFS 非递归遍历算法 * @author Administrator * */ public class DFS { private char[] vertices; //存储顶点信息 private int[][] arcs; //存储边 private boolean[] visited; //顶点是否访问过 private int vexnum; //顶点个娄 /** * 实例对象时需要传入的顶点的个数 * @param n */ public DFS(int n) { vexnum = n; vertices = new char[n]; arcs = new int[n][n]; visited = new boolean[n]; } /** * 在顶点之间添加一条边 * @param i * @param j */ public void AddEdge(int i, int j) { if(i == j) return; arcs[i][j] = 1; arcs[j][i] = 1; } /** * 设置顶点的值 * @param vertices */ public void SetVertices(char[] vertices) { this.vertices = vertices; } /** * 访问第i个顶点元素 * @param i */ private void visit(int i) { System.out.print(" "+this.vertices[i]); } /** * 非递归实现 */ public void DFSByStack() { //初始化访问矩阵 for(int i = 0; i<vexnum;i++) { visited[i] = false; } Stack<Integer> stack = new Stack<Integer>(); stack.push(0); //将第0个元素压入栈 visited[0] = true; //第0个元素已经访问 visit(0); while(!stack.empty()) { int k = stack.peek().intValue(); //访问栈顶元素但不出栈 boolean needPop = true; for(int i=0;i<vexnum; i++) { if(arcs[k][i] == 1 && visited[i] == false) { stack.push(i); //将第i个元素压入栈 visited[i] = true; //第i个元素已经访问 visit(i); needPop = false; break; } } if(needPop) { stack.pop(); } } } /****************************************下面为递归实现相关的代码************************************/ /** * 当前结点的第一个邻接结点在邻接矩阵中的索引 * @param i * @return */ private int FirstNeighbor(int i) { for(int k =i;k<vexnum;k++) { if(arcs[i][k] == 1) { return k; } } return -1; //表示没有相连接点 } /** * 获取i顶点除j外的下一个连接点 * @param i * @param j * @return */ public int NextNeighbor(int i,int j) { for( int k = j + 1; k<vexnum;k++) { if(arcs[i][k] == 1) { return k; } } return -1; } /** * 内部方法 * @param isVisited * @param i */ private void _DFStraverse(boolean[] isVisited,int i) { visited[i] = true; visit(i); int first = FirstNeighbor(i); while(first!=-1) { if(visited[first] == false) { _DFStraverse(isVisited,first); } first = NextNeighbor(i, first); } } /** * 对外方法 */ public void DFStraverse() { //初始化访问矩阵 for(int k = 0; k<vexnum;k++) { visited[k] = false; } for(int k = 0; k<vexnum;k++) { if(!visited[k]) { _DFStraverse(visited,k); } } } /****************************递归方式二*************************************/ /** * 从第i个节点开始深度优先遍历 * @param i */ private void traverse(int i) { visited[i] = true; visit(i); for(int j=0;j<vexnum;j++) // 遍历邻接矩阵中第i个节点的直接联通关系 { if(arcs[i][j]==1 && visited[j]==false) { traverse(j); // 目标节点与当前节点直接联通，并且该节点还没有被访问，递归 } } } public void DFSTraverse2() { for (int i = 0; i < vexnum; i++) { visited[i] = false; } for(int i=0;i<vexnum;i++) { if(visited[i]==false) { traverse(i); } } } }

测试类：

package com.dfs; public class MainClass { public static void main(String[] args) { char[] vertices = {'A','B','C','D','E','F','G','H','I'}; DFS dfs = new DFS(8); dfs.SetVertices(vertices); dfs.AddEdge(0, 1); dfs.AddEdge(0, 5); dfs.AddEdge(1, 0); dfs.AddEdge(1, 2); dfs.AddEdge(1, 3); dfs.AddEdge(1, 4); dfs.AddEdge(2, 1); dfs.AddEdge(2, 6); dfs.AddEdge(3, 1); dfs.AddEdge(3, 7); dfs.AddEdge(4, 1); dfs.AddEdge(5, 0); System.out.println("非递归结果："); dfs.DFSByStack(); System.out.println("\n下一个邻接点递归结果："); dfs.DFStraverse(); } }