【数据结构】图（深度优先遍历、广度优先遍历）的JAVA代码实现

图的遍历是指从图中的任一顶点出发，对图中的所有顶点访问一次并且只访问一次。图的遍历是图的一种基本操作，图中的许多其他操作也都是建立在遍历的基础之上。在图中，没有特殊的顶点被指定为起始顶点，图的遍历可以从任何顶点开始。图的遍历主要有深度优先搜索和广度优先搜索两种方式。

深度优先搜索算法

算法的思想

从图中的某一个顶点x出发，访问x，然后遍历任何一个与x相邻的未被访问的顶点y，再遍历任何一个与y相邻的未被访问的顶点z……依次类推，直到到达一个所有邻接点都被访问的顶点为止；然后，依次回退到尚有邻接点未被访问过的顶点，重复上述过程，直到图中的全部顶点都被访问过为止。

算法实现的思想

深度优先遍历背后基于堆栈，有两种方式：第一种是在程序中显示构造堆栈，利用压栈出栈操作实现；第二种是利用递归函数调用，基于递归程序栈实现。本文介绍第一种方式：

1. 访问起始顶点，并将其压入栈中；
2. 从栈中弹出最上面的顶点，将与其相邻的未被访问的顶点压入栈中；
3. 重复第二步，直至栈为空栈。

未被访问的顶点怎么识别呢？利用visited数组来进行标记。

算法的实现

基于邻接矩阵的算法实现：

	public String depthFirstSearch(int v) {
		if (v < 0 || v >= numOfVexs)
			throw new ArrayIndexOutOfBoundsException();
		visited = new boolean[numOfVexs];
		StringBuilder sb = new StringBuilder();
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(v);
		visited[v] = true;
		while (!stack.isEmpty()) {
			v = stack.pop();
			sb.append(vexs[v] + ",");
			for (int i = numOfVexs - 1; i >= 0; i--) {
				if ((edges[v][i] != 0 && edges[v][i] != Integer.MAX_VALUE)
						&& !visited[i]) {
					stack.push(i);
					visited[i] = true;
				}
			}
		}
		return sb.length() > 0 ? sb.substring(0, sb.length() - 1) : null;
	}

基于邻接表的算法实现：

	public String depthFirstSearch(int v) {
		if (v < 0 || v >= numOfVexs)
			throw new ArrayIndexOutOfBoundsException();
		visited = new boolean[numOfVexs];
		StringBuilder sb = new StringBuilder();
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(v);
		visited[v] = true;
		ENode current;
		while (!stack.isEmpty()) {
			v = stack.pop();
			sb.append(vexs[v].data + ",");
			current = vexs[v].firstadj;
			while (current != null) {
				if (!visited[current.adjvex]) {
					stack.push(current.adjvex);
					visited[current.adjvex] = true;
				}
				current = current.nextadj;
			}
		}
		return sb.length() > 0 ? sb.substring(0, sb.length() - 1) : null;
	}

广度优先搜索算法

算法的思想

从图中的某一个顶点x出发，访问x，然后访问与x所相邻的所有未被访问的顶点x1、x2……xn，接着再依次访问与x1、x2……xn相邻的未被访问的所有顶点。依次类推，直至图中的每个顶点都被访问。

算法实现的思想

广度优先遍历背后基于队列，下面介绍一下具体实现的方法：

1. 访问起始顶点，并将插入队列；
2. 从队列中删除队头顶点，将与其相邻的未被访问的顶点插入队列中；
3. 重复第二步，直至队列为空。

未被访问的顶点怎么识别呢？利用visited数组来进行标记。

算法的实现

基于邻接矩阵的算法实现：

	public String breadFirstSearch(int v) {
		if (v < 0 || v >= numOfVexs)
			throw new ArrayIndexOutOfBoundsException();
		visited = new boolean[numOfVexs];
		StringBuilder sb = new StringBuilder();
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.offer(v);
		visited[v] = true;
		while (!queue.isEmpty()) {
			v = queue.poll();
			sb.append(vexs[v] + ",");
			for (int i = 0; i < numOfVexs; i++) {
				if ((edges[v][i] != 0 && edges[v][i] != Integer.MAX_VALUE)
						&& !visited[i]) {
					queue.offer(i);
					visited[i] = true;
				}
			}
		}
		return sb.length() > 0 ? sb.substring(0, sb.length() - 1) : null;
	}

基于邻接表的算法实现：

	public String breadFirstSearch(int v) {
		if (v < 0 || v >= numOfVexs)
			throw new ArrayIndexOutOfBoundsException();
		visited = new boolean[numOfVexs];
		StringBuilder sb = new StringBuilder();
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.offer(v);
		visited[v] = true;
		ENode current;
		while (!queue.isEmpty()) {
			v = queue.poll();
			sb.append(vexs[v].data + ",");
			current = vexs[v].firstadj;
			while (current != null) {
				if (!visited[current.adjvex]) {
					queue.offer(current.adjvex);
					visited[current.adjvex] = true;
				}
				current = current.nextadj;
			}
		}
		return sb.length() > 0 ? sb.substring(0, sb.length() - 1) : null;
	}

这边的其他的主要部分（如成员变量的定义等），参考【数据结构】图（邻接矩阵、邻接表）的JAVA代码实现。