Java学习-Day17

图的广度优先遍历

一、描述

从随机一个节点出发, 访问该节点所有的邻接节点. 访问后的节点(包括第一个节点)对其进行标记, 若节点未被访问则添加到队列中.

若队列中存在元素就将其出队, 并用上述的方法重复过程.

二、举例

目前存在一个图如下所示

假设从 2 这个节点开始遍历, 2 先标记为访问后入队.

此时队列中有 2 就出队访问 0 和 3, 同时这两个数标记后入队.

0 出队后访问 1 和 2, 但此时的 2 已经被访问过, 就只有 1 入队, 此时 3 出队 访问 1 和 2. 同理 1 2 被访问过就不处理了.

此时队列中只剩一个 1 , 出队后发现 0 3 被访问. 最后队列为空, 遍历完成. 那么遍历的顺序就应该是 2 -> 0 -> 3 -> 1

注：这里这些情况只用于所有节点连通的情况, 要保证不连通节点也被访问到就需要利用一个循环, 对以每一个未访问节点为开始做一次广度有限遍历.

三、具体实现

输入

一个正整数表示从哪个节点开始

输出

由数字组成的字符串, 用以表示广度遍历的顺序. 如在二的图中, 输出如下 

1
2031
### 代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/**
 *********************
 * Breadth first traversal.
 * 
 * @param paraStartIndex The start index.
 * @return The sequence of the visit.
 *********************
 */
public String breadthFirstTraversal(int paraStartIndex) {
	CircleObjectQueue tempQueue = new CircleObjectQueue();
	String resultString = "";

	int tempNumNodes = connectivityMatrix.getRows();
	boolean[] tempVisitedArray = new boolean[tempNumNodes];

	// Initialize the queue.
	// Visit before enqueue.
	tempVisitedArray[paraStartIndex] = true;
	resultString += paraStartIndex;
	tempQueue.enqueue(Integer.valueOf(paraStartIndex));

	// Now visit the rest of the graph.
	int tempIndex;
	Integer tempInteger = (Integer) tempQueue.dequeue();
	while (tempInteger != null) {
		tempIndex = tempInteger.intValue();

		// Enqueue all its unvisited neighbors.
		for (int i = 0; i < tempNumNodes; i++) {
			if (tempVisitedArray[i]) {
				continue; // Already visited.
			} // Of if

			if (connectivityMatrix.getData()[tempIndex][i] == 0) {
				continue; // Not directly connected.
			} // Of if

			// Visit before enqueue.
			tempVisitedArray[i] = true;
			resultString += i;
			tempQueue.enqueue(Integer.valueOf(i));
		} // Of for i

		// Take out one from the head.
		tempInteger = (Integer) tempQueue.dequeue();
	} // Of while

	return resultString;
}// Of breadthFirstTraversal

/**
 *********************
 * Unit test for breadthFirstTraversal.
 *********************
 */
public static void breadthFirstTraversalTest() {
	// Test an undirected graph.
	int[][] tempMatrix = { { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 1 }, { 0, 1, 1, 0 } };
	Graph tempGraph = new Graph(tempMatrix);
	System.out.println(tempGraph);

	String tempSequence = "";
	try {
		tempSequence = tempGraph.breadthFirstTraversal(2);
	} catch (Exception ee) {
		System.out.println(ee);
	} // Of try.

	System.out.println("The breadth first order of visit: " + tempSequence);
}// Of breadthFirstTraversalTest

运行截图

图的深度优先遍历

一、描述

和广度优先遍历不一样的是, 深度优先遍历使用的栈. 它的过程更像是走迷宫, 不管遇到什么选择都一直走到底, 然后再折返走另一条路.

简单点描述就是不撞南墙不回头.

二、举例

同样这里用一个图来解释, 图如下所示.

深度优先遍历通常是从邻接表的第一个节点开始, 当遇到有分支的情况就把其他分支相连的节点放到栈中用于折返时选择.

那么我们也从 0 开始, 为了更符合计算机, 扫描顺序是跟着邻接表走的. 那么就该访问 1 节点, 和广度遍历一样, 遍历后的节点要做标记.

访问 1 节点后 就该访问 3 节点, 访问 3 节点后访问 2 节点, 此时发现无路可走就折返回去. 发现之前的分支都被访问过了, 此时遍历结束. 遍历节点顺序为 0->1->3->2

注：和广度优先遍历一样,这里这些情况只用于所有节点连通的情况, 要保证不连通节点也被访问到就需要利用一个循环, 对以每一个未访问节点为开始做一次深度有限遍历.

三、具体实现

输入

无

输出

由数字组成的字符串, 用以表示广度遍历的顺序. 如在二的图中, 输出如下 

1
0132
### 代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/**
 *********************
 * Depth first traversal.
 * 
 * @param paraStartIndex The start index.
 * @return The sequence of the visit.
 *********************
 */
public String depthFirstTraversal(int paraStartIndex) {
	ObjectStack tempStack = new ObjectStack();
	String resultString = "";

	int tempNumNodes = connectivityMatrix.getRows();
	boolean[] tempVisitedArray = new boolean[tempNumNodes];

	// Initialize the stack.
	// Visit before push.
	tempVisitedArray[paraStartIndex] = true;
	resultString += paraStartIndex;
	tempStack.push(Integer.valueOf(paraStartIndex));
	System.out.println("Push " + paraStartIndex);
	System.out.println("Visited " + resultString);

	// Now visit the rest of the graph.
	int tempIndex = paraStartIndex;
	int tempNext;
	Integer tempInteger;
	while (true) {
		// Find an unvisited neighbor.
		tempNext = -1;
		for (int i = 0; i < tempNumNodes; i++) {
			if (tempVisitedArray[i]) {
				continue; // Already visited.
			} // Of if

			if (connectivityMatrix.getData()[tempIndex][i] == 0) {
				continue; // Not directly connected.
			} // Of if

			// Visit this one.
			tempVisitedArray[i] = true;
			resultString += i;
			tempStack.push(Integer.valueOf(i));
			System.out.println("Push " + i);
			tempNext = i;

			// One is enough.
			break;
		} // Of for i

		if (tempNext == -1) {
			tempInteger = (Integer) tempStack.pop();
			System.out.println("Pop " + tempInteger);
			if (tempStack.isEmpty()) {
				// No unvisited neighbor. Backtracking to the last one
				// stored in the stack.
				// Attention: This is the terminate condition!
				break;
			} else {
				// Back to the previous node, however do not remove it.
				tempInteger = (Integer) tempStack.pop();
				tempIndex = tempInteger.intValue();
				tempStack.push(tempInteger);
			} // Of if
		} else {
			tempIndex = tempNext;
		} // Of if
	} // Of while

	return resultString;
}// Of depthFirstTraversal

/**
 *********************
 * Unit test for depthFirstTraversal.
 *********************
 */
public static void depthFirstTraversalTest() {
	// Test an undirected graph.
	int[][] tempMatrix = { { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 0 }, { 0, 1, 0, 0 } };
	Graph tempGraph = new Graph(tempMatrix);
	System.out.println(tempGraph);

	String tempSequence = "";
	try {
		tempSequence = tempGraph.depthFirstTraversal(0);
	} catch (Exception ee) {
		System.out.println(ee);
	} // Of try.

	System.out.println("The depth first order of visit: " + tempSequence);
}// Of depthFirstTraversalTest

运行截图

总结

广度优先遍历和深度优先遍历巧妙地利用了队列和栈

广度优先遍历的复杂度与深度优先遍历的复杂度大体一致，不同之处在于遍历的方式与对于问题的解决出发点不同, 广度优先遍历适合大范围的寻找, 而深度优先遍历适合目标明确.

总的来说都是穷举.