深度优先搜索算法(java语言)

更新时间:2023-07-24 00:29:52 阅读: 评论:0

深度优先搜索算法(java语⾔)
我们在学习了图之后,需要⼀种机制来遍历图,图的遍历算法也叫图搜索算法。与树的遍历算法(中序、前序、后序以及层序遍历)⼀样,图搜索算法也可以看做从图的某个源点开始,通过遍历和标记顶点来搜索图。下⾯讨论两种遍历图的算法:
(1)深度优先搜索(DFS)。
(2)⼴度优先搜索(BFS)。
⼀、深度优先搜索
例⼦如下图所⽰:
考研政治预测
从该图的基础上遍历该图:
使⽤深度优先搜索算法(DFS),使⽤了两种⽅法,递归和⾮递归⽅法:
import java.util.Stack;
public class DFSTest {
// 存储节点信息
private char[] vertices;
// 存储边信息(邻接矩阵)
private  int[][] arcs;哀鸣
// 图的节点数
private int vexnum;
// 记录节点是否已被遍历
private boolean[] visited;
// 初始化
public DFSTest(int n) {
vexnum = n;
vertices = new char[n];
arcs = new int[n][n];
visited = new boolean[n];
for (int i = 0; i < vexnum; i++) {
innovafor (int j = 0; j < vexnum; j++) {
arcs[i][j] = 0;
}
cret}
}
// 添加边(⽆向图)
public void addEdge(int i, int j) {
// 边的头尾不能为同⼀节点
// 边的头尾不能为同⼀节点
if (i == j)return;
arcs[i][j] = 1;
arcs[j][i] = 1;
}
// 设置节点集
public void tVertices(char[] vertices) {
this.vertices = vertices;
}
// 设置节点访问标记
public void tVisited(boolean[] visited) {
this.visited = visited;
}
// 打印遍历节点
public void visit(int i){
System.out.print(vertices[i] + " ");
}
/
/ 从第i个节点开始深度优先遍历
private void traver(int i){
// 标记第i个节点已遍历
visited[i] = true;
// 打印当前遍历的节点
visit(i);
// 遍历邻接矩阵中第i个节点的直接联通关系
for(int j=0;j<vexnum;j++){
// ⽬标节点与当前节点直接联通,并且该节点还没有被访问,递归            if(arcs[i][j]==1 && visited[j]==fal){
traver(j);
}
}
}
// 图的深度优先遍历(递归)
public void DFSTraver(){
// 初始化节点遍历标记
for (int i = 0; i < vexnum; i++) {
visited[i] = fal;
}
// 从没有被遍历的节点开始深度遍历
eachoffor(int i=0;i<vexnum;i++){
if(visited[i]==fal){
/
/ 若是连通图,只会执⾏⼀次
traver(i);
}
}
}
// 图的深度优先遍历(⾮递归)
public void DFSTraver2(){
// 初始化节点遍历标记
for (int i = 0; i < vexnum; i++) {
visited[i] = fal;
}
放鸽子英文
Stack<Integer> s = new Stack<Integer>();
for(int i=0;i<vexnum;i++){
if(!visited[i]){
//连通⼦图起始节点
s.add(i);
s.add(i);
do{
// 出栈
int curr = s.pop();
// 如果该节点还没有被遍历,则遍历该节点并将⼦节点⼊栈                    if(visited[curr]==fal){
// 遍历并打印
visit(curr);
visited[curr] = true;
// 没遍历的⼦节点⼊栈
for(int j=vexnum-1; j>=0 ; j-- ){
if(arcs[curr][j]==1 && visited[j]==fal){
s.add(j);
}
}
}
}while(!s.isEmpty());
}
}
}
public static void main(String[] args) {
english story
DFSTest g = new DFSTest(9);
char[] vertices = {'A','B','C','D','E','F','G','H','I'};
g.tVertices(vertices);
g.addEdge(0, 1);
g.addEdge(0, 5);
g.addEdge(1, 0);
g.addEdge(1, 2);
g.addEdge(1, 6);
g.addEdge(1, 8);
g.addEdge(2, 1);
g.addEdge(2, 3);
g.addEdge(2, 8);
g.addEdge(3, 2);
奥斯卡影片g.addEdge(3, 4);
g.addEdge(3, 6);
g.addEdge(3, 7);
royan
g.addEdge(3, 8);
g.addEdge(4, 3);
g.addEdge(4, 5);
g.addEdge(4, 7);
g.addEdge(5, 0);
g.addEdge(5, 4);
g.addEdge(5, 6);
g.addEdge(6, 1);
g.addEdge(6, 3);
g.addEdge(6, 5);
g.addEdge(6, 7);
g.addEdge(7, 3);
g.addEdge(7, 4);
北京澳际中介g.addEdge(7, 6);
g.addEdge(8, 1);
g.addEdge(8, 2);
g.addEdge(8, 3);
System.out.print("深度优先遍历(递归):");
g.DFSTraver();
System.out.println();
System.out.print("深度优先遍历(⾮递归):");
g.DFSTraver2();
g.DFSTraver2();
}
}
执⾏结果截图为:
如果使⽤邻接表来表⽰图,则DFS算法的时间复杂度为O(V+E),如果⽤邻接矩阵来表⽰图,时间复杂度为O(V平⽅)DFS的应⽤:⽣成森林、连同分量、路径、环路且内存开销⽐BFS要⼩很多。
ps:BFS算法和这两者的区别下⼀节我会介绍!
最后:欢迎⼤家评论交流,互相学习,共同进步!

本文发布于:2023-07-24 00:29:52,感谢您对本站的认可!

本文链接:https://www.wtabcd.cn/fanwen/fan/90/186773.html

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

标签:遍历   节点   深度   优先   算法   环路
相关文章
留言与评论(共有 0 条评论)
   
验证码:
Copyright ©2019-2022 Comsenz Inc.Powered by © 专利检索| 网站地图