DFS深度优先搜索算法与BFS广度优先搜索算法的java实现

程序员文章站 2022-05-20 19:06:15

...

广度优先搜索算法

package graph;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Stack;

public class BFS {
	public class Node{
		/**
		 * 节点的标识符
		 */
		private Integer identifier;
		/**
		 * 该节点是否被访问过
		 */
		private boolean visited = false;
		/**
		 * 该节点与其他节点的映射关系
		 */
		private Map<Node,Integer> mapping = new HashMap<Node,Integer>();

		public Integer getIdentifier() {
			return identifier;
		}
		public void setIdentifier(Integer identifier) {
			this.identifier = identifier;
		}
		public boolean isVisited() {
			return visited;
		}
		public void setVisited(boolean visited) {
			this.visited = visited;
		}
		public Map<Node, Integer> getMapping() {
			return mapping;
		}
	}
	public static Stack<Node> searchByBFS(Node src, Node target) {
		// TODO Auto-generated method stub
		return bfs(src, target, false, new Stack<Node>());
	}
	/**
	 * 广度优先搜索
	 * 遍历起点的所有相邻节点，若无目标节点，选择一个节点为起点继续递归搜索
	 * 若已无未被访问过的相邻节点，则结束本次递归，该节点出栈
	 * @param src 起点
	 * @param target 目标节点
	 * @param isFound 是否已搜索到
	 * @param path 记录路径
	 * @return 路径栈
	 */
	public static Stack<Node> bfs(Node src, Node target, boolean isFound, Stack<Node> path) {
		if(!isFound) {
			path.add(src);
			Map<Node, Integer> mapping = src.getMapping();
			Iterator<Entry<Node, Integer>> entryIterator = mapping.entrySet().iterator();
			while (entryIterator.hasNext()) {
				Map.Entry<Node, Integer> entry = (Map.Entry<Node, Integer>) entryIterator.next();
				Node nextNode = entry.getKey();
				if (nextNode.getIdentifier() == target.getIdentifier()) {
					isFound = true;
					path.add(nextNode);
					return path;
				}
			}
			//在src的相邻节点中未找到target，则选择一个相邻节点作为src开始递归
			entryIterator = mapping.entrySet().iterator();
			while (entryIterator.hasNext()) {
				Map.Entry<Node, Integer> entry = (Map.Entry<Node, Integer>) entryIterator.next();
				Node nextNode = entry.getKey();
				if(!path.contains(nextNode) && nextNode.getMapping().size() != 0) {
					Stack<Node> temp = bfs(nextNode, target, isFound, path);
					if(temp == null) {
						continue;
					}
					return temp;
				}
			}
			if(!isFound) {
				path.remove(src);
				return null;
			}
		}
		return path;
	}
}

测试：

package graph.test;

import graph.BFS;
import graph.BFS.Node;
import graph.DFS;

import java.util.Iterator;
import java.util.Stack;

public class BFSTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BFS bfs = new BFS();
		BFS.Node node_1 = bfs.new Node();
		BFS.Node node_2 = bfs.new Node();
		BFS.Node node_3 = bfs.new Node();
		BFS.Node node_4 = bfs.new Node();
		BFS.Node node_5 = bfs.new Node();
		BFS.Node node_6 = bfs.new Node();
		
		node_1.setIdentifier(1);
		node_1.getMapping().put(node_2, 7);
		node_1.getMapping().put(node_3, 9);
		node_1.getMapping().put(node_6, 14);
		
		node_2.setIdentifier(2);
		node_2.getMapping().put(node_1, 7);
		node_2.getMapping().put(node_3, 10);
		node_2.getMapping().put(node_4, 15);
		
		node_3.setIdentifier(3);
		node_3.getMapping().put(node_1,7);
		node_3.getMapping().put(node_2,10);
		node_3.getMapping().put(node_4,11);
		node_3.getMapping().put(node_6,2);
		
		node_4.setIdentifier(4);
		node_4.getMapping().put(node_3, 11);
		node_4.getMapping().put(node_2, 15);
		node_4.getMapping().put(node_5, 6);
		
		node_5.setIdentifier(5);
		node_5.getMapping().put(node_4, 6);
		node_5.getMapping().put(node_6, 9);
		
		node_6.setIdentifier(6);
		node_6.getMapping().put(node_5, 9);
		node_6.getMapping().put(node_1, 14);
		
		Stack<Node> path = BFS.searchByBFS(node_2, node_6);
		System.out.println("-------The BFS path--------");
		for (Iterator<Node> iterator = path.iterator(); iterator.hasNext();) {
			Node node = (Node) iterator.next();
			if (iterator.hasNext()) {
				System.out.print(node.getIdentifier()+"-->");
			}else{
				System.out.print(node.getIdentifier());
			}
		}
	}

}

结果：

DFS深度优先搜索算法与BFS广度优先搜索算法的java实现
--------------------------------------------------------------分隔线--------------------------------------------------------------------

深度有限

package graph;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Stack;

/**
 * Depth first search
 * @author Administrator
 *
 */
public class DFS {
	public class Node{
		/**
		 * 节点的标识符
		 */
		private Integer identifier;
		/**
		 * 该节点是否被访问过
		 */
		private boolean visited = false;
		/**
		 * 该节点与其他节点的映射关系
		 */
		private Map<Node,Integer> mapping = new HashMap<Node,Integer>();

		public Integer getIdentifier() {
			return identifier;
		}
		public void setIdentifier(Integer identifier) {
			this.identifier = identifier;
		}
		public boolean isVisited() {
			return visited;
		}
		public void setVisited(boolean visited) {
			this.visited = visited;
		}
		public Map<Node, Integer> getMapping() {
			return mapping;
		}
	}
	
	public static Stack<Node> searchByDFS(Node src, Node target) {
		return dfs(src, target, false, new Stack<Node>());
	}
	
	/**
	 * 深度优先搜索算法
	 * 从起始节点开始，判断相邻的第一个未被访问的节点，若不是目标节点，
	 * 且该节点还有未被访问的节点，则该节点入栈并递归。
	 * 局部递归结束条件：
	 * 1、若没有下一个未被访问的相邻节点，则该节点出栈
	 * 2、搜索到目标节点，该节点入栈，结束递归
	 * @param src 起始节点
	 * @param target 目标节点
	 * @param path 路径栈
	 * @return 路径栈
	 */
	public static Stack<Node> dfs(Node src, Node target, boolean isFound, Stack<Node> path){
		//未找到目标节点，起始时判断可提高性能
		if(!isFound){
			//当前节点入栈
			path.add(src);
			//遍历相邻节点
			Map<Node, Integer> mapping = src.getMapping();
			Iterator<Entry<Node, Integer>> entryIterator = mapping.entrySet().iterator();
			while (entryIterator.hasNext()) {
				//未找到目标节点
				Entry<Node, Integer> entry = (Entry<Node, Integer>) entryIterator.next();
				Node nextNode = entry.getKey();
				//判断下一节点是否在路径中
				if(!path.contains(nextNode)){
					//判断是否为目标节点
					if(nextNode.getIdentifier() == target.getIdentifier()) {
						isFound = true;
						path.add(nextNode);
						break;
					}
					//不是目标节点，且下一节点仍有相邻节点，则以nextNode作为下一递归的src
					if(nextNode.getMapping().size() != 0) {
						Stack<Node> temp = dfs(nextNode, target, isFound, path);
						if(temp == null) continue;
						return temp;
					}
				}
			}
			//没有下一个未被访问的相邻节点且未找到目标节点，当前节点出栈，回溯
			if(!isFound) {
				path.remove(src);
				return null;
			}
		}
		return path;
	}
}

测试：

package graph.test;

import graph.DFS;
import graph.DFS.Node;

import java.util.Iterator;
import java.util.Stack;

public class DFSTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		DFS dfs = new DFS();
		DFS.Node node_1 = dfs.new Node();
		DFS.Node node_2 = dfs.new Node();
		DFS.Node node_3 = dfs.new Node();
		DFS.Node node_4 = dfs.new Node();
		DFS.Node node_5 = dfs.new Node();
		DFS.Node node_6 = dfs.new Node();
		
		node_1.setIdentifier(1);
		node_1.getMapping().put(node_2, 7);
		node_1.getMapping().put(node_3, 9);
		node_1.getMapping().put(node_6, 14);
		
		node_2.setIdentifier(2);
		node_2.getMapping().put(node_1, 7);
		node_2.getMapping().put(node_3, 10);
		node_2.getMapping().put(node_4, 15);
		
		node_3.setIdentifier(3);
		node_3.getMapping().put(node_1,7);
		node_3.getMapping().put(node_2,10);
		node_3.getMapping().put(node_4,11);
		node_3.getMapping().put(node_6,2);
		
		node_4.setIdentifier(4);
		node_4.getMapping().put(node_3, 11);
		node_4.getMapping().put(node_2, 15);
		node_4.getMapping().put(node_5, 6);
		
		node_5.setIdentifier(5);
		node_5.getMapping().put(node_4, 6);
		node_5.getMapping().put(node_6, 9);
		
		node_6.setIdentifier(6);
		node_6.getMapping().put(node_5, 9);
		node_6.getMapping().put(node_1, 14);
		
		Stack<Node> path = DFS.searchByDFS(node_1, node_6);
		System.out.println("-------The DFS path--------");
		for (Iterator<Node> iterator = path.iterator(); iterator.hasNext();) {
			Node node = (Node) iterator.next();
			if (iterator.hasNext()) {
				System.out.print(node.getIdentifier()+"-->");
			}else{
				System.out.print(node.getIdentifier());
			}
		}
	}

}

结果：

DFS深度优先搜索算法与BFS广度优先搜索算法的java实现

DFS深度优先搜索算法与BFS广度优先搜索算法的java实现

PHP实现二叉树的深度优先与广度优先遍历方法

Python数据结构与算法之图的广度优先与深度优先搜索算法示例

可能是目前为止最为详细的深度优先搜索DFS和广度优先搜索BFS算法分析

数据结构与算法-----BFS与DFS（广度优先搜索与深度优先搜索）

数据结构与算法_深度优先搜索（DFS）与广度优先搜索（BFS）详解

Java数据结构与算法：图、图的概念、深度优先搜索DFS、广度优先搜索BFS、思路分析、代码实现

【数据结构】图的遍历——深度优先搜索DFS、广度优先搜索BFS

BFS（广度优先搜索算法）和DFS（深度优先搜索算法）

数据结构与算法————图的遍历DFS深度优先搜索和BFS广度优先搜索

JavaScript实现树的遍历算法示例【广度优先与深度优先】