数据结构 图论5 DFS和BFS深度优先搜索和广度优先搜索详解 java
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构 图论5 DFS和BFS深度优先搜索和广度优先搜索详解 java，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4560字，纯文字阅读大概需要7分钟。
内容图文
阅读前请先了解邻接矩阵
DFS深度优先搜索
DFS（Deep First Search），递归最深度访问其所有的临近节点（类似二叉树先序遍历);
比如A节点的临近节点就是C，D；C的临近节点就是A，B；
访问临近节点的优先级是A --> B --> C --> D --> E --> F,比如说A有C，D2个临近节点就会先访问C节点；
访问过的节点不再访问（通过visited标记）
例如：下面以A节点为起始点
- 访问A节点，然后按照优先级访问C节点
- C节点的邻近节点A已经visited，访问B节点
- B节点D邻近节点C已经visited，B没有可以访问的节点，回退到A节点（类似二叉树先序遍历);
- A节点向D节点访问
- D节点 的 A，C邻近节点都已经visited，访问E节点
- E节点的D邻近节点已经visited，访问F节点
注意这里访问并没有结束，因为我们还有很多分支没有遍历，优先级 “A --> B --> C --> D --> E --> F”,所以我们按照原路返回。（类似先序遍历）
- 回退到E节点，E节点的所有邻近节点都visited
- 回退到D节点，（检查F节点，不是邻近节点）D节点的所有邻近节点都visited
- 回退到A节点，（检查E，F节点，不是邻近节点）A节点的所有邻近节点都visited
DFS结束 输出的顺序依次是 A --> C --> B --> D --> E --> F （0 - 2 - 1 - 3 - 4 - 5 ）
代码
public class DFS {
//A, B, C,D, E, F
static int[][] graph = new int[][]{
{0, 0, 1, 1, 0, 0},
{0, 0, 1, 0, 0, 0},
{1, 1, 0, 0, 0, 0},
{0, 0, 1, 0, 1, 0},
{0, 0, 0, 1, 0, 1},
{0, 0, 0, 0, 1, 0}};
static int[] visited = new int[graph.length];//用来记录已经遍历过的元素
//DFS(深度优先遍历)同样适用于有向图 A->C->B->D->E->F 即 0->2->1->3->4->5
public static void dfsTraversing(int node, int[][] graph) {
//遍历输出
visited[node]=1;
System.out.println(node);
//循环一个长度
for (int i = 0; i < graph[node].length; ++i) {
//visited = 0；就是这个节点没有visited
//i != node 就是传入的visited节点不是node，我们需要以node节点的下一个节点为基础，DFS
//graph[node][i] == 1 保证这个node节点的下一个节点是可以通行的
if (visited[i]==0&&i != node&&graph[node][i]==1) {
dfsTraversing(i, graph);
}
}
}
}
BFS 广度优先遍历
广度优先遍历类似树的层序遍历，比如我们将一个图按照起始点为A展开。
先遍历第一层，A；然后遍历第二层 C ，D；然后遍历第三层 B，E，最后遍历第四层 F。
利用队列来实现
每次poll出一个节点就将这个节点没有visited过的邻近点offer推入队列（比如A出队列，C，D就如队列）
入队列Queue的时候输出节点
例如：下面以A为起始节点
- A入队列。输出A
（queue={A}) - A出队列 ，A的没有visited的邻近节点 C ，D入队列。输出C，D；
（queue={C,D}) - C出队列，C周围没有visited的B节点入队列；D出队列，D周围没有visited的节点E入队列。输出B，E；
（queue={B,E}) - B出队列，B周围都已经visited；E出队列E周围没有visited的F入队列。输出F；
（queue={F}) - F出队列，B周围都已经visited，且队列里面没有值，循环结束，程序结束
代码
public static void bfs(int[][] graph,int firstNode){
LinkedList<Integer> queue = new LinkedList<>();
int length = graph.length;
System.out.println(firstNode);
visited[firstNode] = true;
queue.offer(firstNode);
while (queue.size() > 0){
//poll出一个值
int node = queue.poll();
//遍历这个行
for (int i = 0; i < length; i++) {
//如果行中有可以通行的点i
//并且这个通行的点i没visited
if (graph[node][i] != 0 && visited[i] == false) {
System.out.println(i);
//标记visited
visited[i] = true;
//就将这个点i入队列
queue.offer(i);
}
}
}
}
总代码
public class DfsAndBfs {
/**
* A,B,C,D,E,F
* 0,1,2,3,4,5
*/
private int[][] graph;
/**
* visited用来记录已经遍历过的元素
*/
private boolean[] visited;
public DfsAndBfs(int[][] graph) {
this.graph = graph;
visited = new boolean[graph.length];
}
/**
* BFS(广度优先遍历) 基于队列实现
*/
public void bfs( int firstNode) {
LinkedList<Integer> queue = new LinkedList<>();
int length = graph.length;
System.out.println(firstNode);
visited[firstNode] = true;
queue.offer(firstNode);
while (queue.size() > 0) {
//poll出一个值
int node = queue.poll();
//遍历这个行
for (int i = 0; i < length; i++) {
//如果行中有可以通行的点i
//并且这个通行的点i没visited
if (graph[node][i] != 0 && visited[i] == false) {
System.out.println(i);
//标记visited
visited[i] = true;
//就将这个点i入队列
queue.offer(i);
}
}
}
}
/**
* DFS 深度优先遍历 递归实现
* （也可通过栈实现，因为递归的本质就是压栈）
*/
public void dfs(int node) {
//遍历输出
visited[node] = true;
System.out.println(node);
//循环一个长度
for (int i = 0; i < graph[node].length; ++i) {
//visited = false；就是这个节点没有visited
//i != node 就是传入的visited节点不是node，我们需要以node节点的下一个节点为基础，DFS
//graph[node][i] == 1 保证这个node节点的下一个节点是可以通行的
if (visited[i] == false && i != node && graph[node][i] == 1) {
dfs(i);
}
}
}
}
test
int[][] graph = new int[][]{
{0, 0, 1, 1, 0, 0},
{0, 0, 1, 0, 0, 0},
{1, 1, 0, 0, 0, 0},
{0, 0, 1, 0, 1, 0},
{0, 0, 0, 1, 0, 1},
{0, 0, 0, 0, 1, 0}};
//0 2 1 3 4 5
new DfsAndBfs(graph).dfs(0);
System.out.println("==========");
//因为遍历会改变visited的值，所以需要重新构造对象
//0 2 3 1 4 5
new DfsAndBfs(graph).bfs(0);
refrence：
内容总结
以上是互联网集市为您收集整理的数据结构 图论5 DFS和BFS深度优先搜索和广度优先搜索详解 java全部内容，希望文章能够帮你解决数据结构 图论5 DFS和BFS深度优先搜索和广度优先搜索详解 java所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。