Question

图的DFS遍历 先任意创建一个图； 图的DFS的递归和非递归算法的实现 用邻接矩阵、邻接表两种结构存储实现

图的DFS遍历

要求：
1) 先任意创建一个图；
2) 图的DFS的递归和非递归算法的实现
3) 要求用邻接矩阵、邻接表两种结构存储实现
谁有代码啊 急需啊

Answer 1

package com.graphic;

public class DFS_Graph {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int matrix[][] = { { 0, 1, 0, 0, 1 }, { 1, 0, 1, 1, 1 },
				{ 0, 1, 0, 1, 0 }, { 0, 1, 1, 0, 1 }, { 1, 1, 0, 1, 0 } };
		DFS_Graph graph = new DFS_Graph();
		graph.init(matrix);

	}

	int time = 0;
	GNode array[];
   
    
	public void init(int matrix[][]) {
		array = new GNode[matrix.length];
		for (int i = 0; i < array.length; i++)// 初始化
		{
			array[i] = new GNode(i);
		}
		for (int i = 0; i < array.length; i++) {
			if (array[i].color.equals("w"))
			{
				DFS(array[i], matrix, array);
				
				for (int j = 0; j < array.length; j++)
				{
					if(j>0)
					{
						System.out.println(array[j].id + " color=" + array[j].color
								+ " d_time=" + array[j].d_time + " f_time="
								+ array[j].f_time+" par= "+array[j].par.id);
					}
					else
					{
						System.out.println(array[j].id + " color=" + array[j].color
								+ " d_time=" + array[j].d_time + " f_time="
								+ array[j].f_time);
					}
				}				
				System.out.println();
				System.out.println();
			}
		}
		// DFS(array[0], matrix, array);
	}

	public void DFS(GNode u, int matrix[][], GNode array[]) {
		u.color = "g";
		time++;
		u.d_time = time;
		for (int i = 0; i < matrix.length; i++) {
			if (matrix[u.id][i] == 1 && array[i].color.equals("w")) {
				array[i].par = u;
				DFS(array[i], matrix, array);
			}
		}
		u.color = "b";
		time++;
		u.f_time = time;
	}
}

class GNode {
	String color;// color=black 没有访问，//color=gray 正在访问//color=black已经访问结束了
	int id;
	int d_time;
	int f_time;
	GNode par;

	public GNode() {
	}

	public GNode(int id) {
		this.color = "w";
		this.d_time = 0;
		this.f_time = 0;
		this.par = null;
		this.id = id;
	}

}

别人写的代码你可能不容易理解的。给你个参考吧：算法导论第二版22章，图的基本算法，里面有关于图的DFS和BFS算法。代码是用伪代码写的，但是讲解很详细，慢慢看，就当做学习的过程吧。