java基础总结(六十四)--【图数据结构的遍历】java实现广度优先和深度优先遍历
程序员文章站
2022-05-20 20:23:30
...
宽度优先搜索(BFS)遍历图需要使用队列queue数据结构; 深度优先搜索(DFS, Depth First Search)的实现
需要使用到栈stack数据结构。
java中虽然有Queue接口,单java并没有给出具体的队列实现类,而Java中让LinkedList类实现了Queue接口,所以使用队列的时候,一般采用LinkedList。因为LinkedList是双向链表,可以很方便的实现队列的所有功能。
java中定义队列 一般这样定义: Queue queue = new LinkedList();
java中的栈由java.util.Stack类实现,是一个后进先出(last in first out,LIFO)的堆栈,在Vector类的基础上扩展5个方法而来。
E push(E item)
把项压入堆栈顶部。
E pop()
移除堆栈顶部的对象,并作为此函数的值返回该对象。
E peek()
查看堆栈顶部的对象,但不从堆栈中移除它。
boolean empty()
测试堆栈是否为空。
int search(Object o)
返回对象在堆栈中的位置,以 1 为基数。
BFS和DFS遍历代码实现如下:
import java.util.*;
/**
* 使用java实现图的图的广度优先 和深度优先遍历算法。
*/
public class GraphLoopTest {
private Map<String, List<String>> graph = new HashMap<String, List<String>>();
/**
* 初始化图数据:使用邻居表来表示图数据。
*/
public void initGraphData() {
// 图结构如下
// 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
// \ | / \ /
// 8 9
graph.put("1", Arrays.asList("2", "3"));
graph.put("2", Arrays.asList("1", "4", "5"));
graph.put("3", Arrays.asList("1", "6", "7"));
graph.put("4", Arrays.asList("2", "8"));
graph.put("5", Arrays.asList("2", "8"));
graph.put("6", Arrays.asList("3", "8", "9"));
graph.put("7", Arrays.asList("3", "9"));
graph.put("8", Arrays.asList("4", "5", "6"));
graph.put("9", Arrays.asList("6", "7"));
}
/**
* 宽度优先搜索(BFS, Breadth First Search)
* BFS使用队列(queue)来实施算法过程
*/
private Queue<String> queue = new LinkedList<String>();
private Map<String, Boolean> status = new HashMap<String, Boolean>();
/**
* 开始点
*
* @param startPoint
*/
public void BFSSearch(String startPoint) {
//1.把起始点放入queue;
queue.add(startPoint);
status.put(startPoint, false);
bfsLoop();
}
private void bfsLoop() {
// 1) 从queue中取出队列头的点;更新状态为已经遍历。
String currentQueueHeader = queue.poll(); //出队
status.put(currentQueueHeader, true);
System.out.println(currentQueueHeader);
// 2) 找出与此点邻接的且尚未遍历的点,进行标记,然后全部放入queue中。
List<String> neighborPoints = graph.get(currentQueueHeader);
for (String poinit : neighborPoints) {
if (!status.getOrDefault(poinit, false)) { //未被遍历
if (queue.contains(poinit)) continue;
queue.add(poinit);
status.put(poinit, false);
}
}
if (!queue.isEmpty()) { //如果队列不为空继续遍历
bfsLoop();
}
}
/**
* 深度优先搜索(DFS, Depth First Search)
* DFS使用队列(queue)来实施算法过程
* stack具有后进先出LIFO(Last Input First Output)的特性,DFS的操作步骤如下:
*/
// 1、把起始点放入stack;
// 2、重复下述3步骤,直到stack为空为止:
// 从stack中访问栈顶的点;
// 找出与此点邻接的且尚未遍历的点,进行标记,然后全部放入stack中;
// 如果此点没有尚未遍历的邻接点,则将此点从stack中弹出。
private Stack<String> stack = new Stack<String>();
public void DFSSearch(String startPoint) {
stack.push(startPoint);
status.put(startPoint, true);
dfsLoop();
}
private void dfsLoop() {
if(stack.empty()){
return;
}
//查看栈顶元素,但并不出栈
String stackTopPoint = stack.peek();
// 2) 找出与此点邻接的且尚未遍历的点,进行标记,然后全部放入queue中。
List<String> neighborPoints = graph.get(stackTopPoint);
for (String point : neighborPoints) {
if (!status.getOrDefault(point, false)) { //未被遍历
stack.push(point);
status.put(point, true);
dfsLoop();
}
}
String popPoint = stack.pop();
System.out.println(popPoint);
}
public static void main(String[] args) {
GraphLoopTest test = new GraphLoopTest();
test.initGraphData();
// test.BFSSearch("1");
test.DFSSearch("1");
}
}
上一篇: 深度优先搜索--N皇后问题
推荐阅读
-
java图的深度优先遍历实现随机生成迷宫
-
Java实现二叉树的深度优先遍历和广度优先遍历算法示例
-
Java数据结构与算法:图、图的概念、深度优先搜索DFS、广度优先搜索BFS、思路分析、代码实现
-
数据结构与算法————图的遍历DFS深度优先搜索和BFS广度优先搜索
-
java数据结构与算法之二叉树深度优先和广度优先遍历
-
数据结构与算法(Java描述)-20、图、图的邻接矩阵、有向图的广度优先遍历与深度优先遍历
-
图的深度优先搜索(DFS)和广度优先搜索(BFS)及其Java实现
-
数据结构与算法1:二叉树(binary_tree)的前、中、后序(深度优先)和广度优先遍历及python代码实现
-
【数据结构】图(深度优先遍历、广度优先遍历)的JAVA代码实现
-
Java数据结构——图的深度优先遍历算法