邻接矩阵表示图的深度优先算法-堆栈实现

 对于邻接矩阵表示的图做深度优先搜索用递归的方式实现起来代码简介，也好说明问题。递归函数是：

void DFSM(MGraph *G,int i)  
{  
    int j;  
    printf("深度优先遍历结点: 结点%c/n",G->vexs[i]);   //访问顶点vi  
    visited[i]=TRUE;          
    for(j=0;j<G->n;j++)           //依次搜索vi邻接点  
        if(G->edges[i][j]==1 && !visited[j])  
            DFSM(G,j);  
}  

堆栈实现就是起到代替程序在执行递归时底层保存函数状态的作用。需要保存的状态一个是i,一个j，因此堆栈实现的深度优先搜索的流程图如下： 

 

 

 

 具体函数代码如下：

public void traverseDfs(int v) {
		boolean[] visited = new boolean[vertexlist.length()];
		VertexStack stack1 = new VertexStack();
		VertexStack stack2 = new VertexStack();
		int i, j = 0, k;

		i = vertexlist.findData(v);
		k = i;

		System.out.println("访问[" + i + "," + j + "]:" + v);
		visited[i] = true;

		while (true) {

			while (j < vertexlist.length()
					&& (adjmatrix[i][j] == 0 || visited[j])) {
				System.out.println("路过[" + i + "," + j + "]:" + v);
				j++;
			}

			if (i == k && j == vertexlist.length()) {
				break;
			}

			if (j == vertexlist.length()) {
				i = stack1.pop();
				j = stack2.pop();
				continue;
			}

			v = vertexlist.getData(j);
			System.out.println("访问[" + i + "," + j + "]:" + v);
			visited[j] = true;

			stack1.push(i);
			stack2.push(j);

			i = j;
			j = 0;

		}

	}