【数据结构】深度优先搜索BFS和广度优先搜索DFS

深度优先是访问结点r，循环访问r的每个相邻结点。在访问r的相邻结点n时，我们会继续访问r的其他相邻结点前，先访问n的所有相邻结点。也就是说，在继续搜索r的其他子结点之前，我们会先穷尽搜索n的子结点

伪代码

void DFS_Search(Node root)

广度优先BFS，我们会在搜索r的孙子结点之前先访问r的相邻结点，用队列迭代实现的方案

伪代码

<pre name="code" class="java">void BFS_Search

import java.util.Queue;


public class DFS_BFS {
	void DFS_Search(Node root) {
		if ( root == null ) return;
		visit(root);
		root.visited = true;
		foreach (Node n in roo.adjacent) {
			DFS_Search(n);
		}
	}
	
	
	void BFS_Search(Node root) {
		Queue<E> queue = new Queue();
		root.visited = true;
		visit(root);
		queue.enqueue(root);//add to the rear of the queue
		
		while( !queue.isEmpty() ) {
			Node r = queue.dequeue(); //remove from the head of the queue
			foreach (Node n in r.adjacent) {
				if (n.visited == false) {
					visit(n);
					n.visited = true;
					queue.enqueue(n);
				}
			}
		}
	}
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!