「java图深度优先」图的深度优先和广度优先

本篇文章给大家谈谈java图深度优先，以及图的深度优先和广度优先对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、求代码，java实验，题目如图
• 2、java如何实现 深度优先 广度优先
• 3、用java编写 深度优先法 寻路时 怎么实现八个方向的路径选择
• 4、深度优先和广度优先 的区别 ，用法。
• 5、怎么用java来设计数据结构中的图，图的结点数和边的关系由用户输入，做了好久弄不出来，求解，非常感谢。
• 6、java 深度优先搜索（回溯法）求集合的幂集

求代码，java实验，题目如图

import java.util.Scanner;

import java.util.Stack;

public class DFS

{

// 存储节点信息

private char[] vertices;

// 存储边信息（邻接矩阵）

private int[][] arcs;

// 图的节点数

private int vexnum;

// 记录节点是否已被遍历

private boolean[] visited;

// 初始化

public DFS(int n)

{

vexnum = n;

vertices = new char[n];

arcs = new int[n][n];

visited = new boolean[n];

for(int i = 0; i  vexnum; i++)

{

for(int j = 0; j  vexnum; j++)

{

arcs[i][j] = 0;

}

}

}

// 添加边(无向图)

public void addEdge(int i, int j)

{

// 边的头尾不能为同一节点

if(i == j)

return;

arcs[i - 1][j - 1] = 1;

arcs[j - 1][i - 1] = 1;

}

// 设置节点集

public void setVertices(char[] vertices)

{

this.vertices = vertices;

}

// 设置节点访问标记

public void setVisited(boolean[] visited)

{

this.visited = visited;

}

// 打印遍历节点

public void visit(int i)

{

System.out.print(vertices[i] + " ");

}

// 从第i个节点开始深度优先遍历

private void traverse(int i)

{

// 标记第i个节点已遍历

visited[i] = true;

// 打印当前遍历的节点

visit(i);

// 遍历邻接矩阵中第i个节点的直接联通关系

for(int j = 0; j  vexnum; j++)

{

// 目标节点与当前节点直接联通，并且该节点还没有被访问，递归

if(arcs[i][j] == 1  visited[j] == false)

{

traverse(j);

}

}

}

// 图的深度优先遍历（递归）

public void DFSTraverse(int start)

{

// 初始化节点遍历标记

for(int i = 0; i  vexnum; i++)

{

visited[i] = false;

}

// 从没有被遍历的节点开始深度遍历

for(int i = start - 1; i  vexnum; i++)

{

if(visited[i] == false)

{

// 若是连通图，只会执行一次

traverse(i);

}

}

}

// 图的深度优先遍历（非递归）

public void DFSTraverse2(int start)

{

// 初始化节点遍历标记

for(int i = 0; i  vexnum; i++)

{

visited[i] = false;

}

StackInteger s = new StackInteger();

for(int i = start - 1; i  vexnum; i++)

{

if(!visited[i])

{

// 连通子图起始节点

s.add(i);

do

{

// 出栈

int curr = s.pop();

// 如果该节点还没有被遍历，则遍历该节点并将子节点入栈

if(visited[curr] == false)

{

// 遍历并打印

visit(curr);

visited[curr] = true;

// 没遍历的子节点入栈

for(int j = vexnum - 1; j = 0; j--)

{

if(arcs[curr][j] == 1  visited[j] == false)

{

s.add(j);

}

}

}

} while(!s.isEmpty());

}

}

}

public static void main(String[] args)

{

Scanner sc = new Scanner(System.in);

int N, M, S;

while(true)

{

System.out.println("输入N M S，分别表示图G的结点数，边数，搜索的起点：");

String line = sc.nextLine();

if(!line.matches("^\\s*([1-9]\\d?|100)(\\s+([1-9]\\d?|100)){2}\\s*$"))

{

System.out.print("输入错误，");

continue;

}

String[] arr = line.trim().split("\\s+");

N = Integer.parseInt(arr[0]);

M = Integer.parseInt(arr[1]);

S = Integer.parseInt(arr[2]);

break;

}

DFS g = new DFS(N);

char[] vertices = new char[N];

for(int i = 0; i  N; i++)

{

vertices[i] = (i + 1 + "").charAt(0);

}

g.setVertices(vertices);

for(int m = 0; m  M; m++)

{

System.out.println("输入图G的第" + (m + 1) + "条边，格式为“i j”，其中i，j为结点编号（范围是1~N）");

String line = sc.nextLine();

if(!line.matches("^\\s*([1-9]\\d?|100)\\s+([1-9]\\d?|100)\\s*$"))

{

System.out.print("输入错误，");

m--;

continue;

}

String[] arr = line.trim().split("\\s+");

int i = Integer.parseInt(arr[0]);

int j = Integer.parseInt(arr[1]);

g.addEdge(i, j);

}

sc.close();

System.out.print("深度优先遍历（递归）：");

g.DFSTraverse(S);

System.out.println();

System.out.print("深度优先遍历（非递归）：");

g.DFSTraverse2(S);

}

}

java如何实现 深度优先 广度优先

下面是我修改了滴源码，是基于一张简单的地图，在地图上搜索目的节点，依次用深度优先、广度优先、Dijkstra算法实现。

import java.util.ArrayList;

import java.util.HashMap;

import java.util.LinkedList;

import java.util.PriorityQueue;

import java.util.Stack;

/**

*

* @author yinzhuo

*

*/

public class Arithmatic {

boolean flag = true;

// 一张地图

static int[][] map = new int[][]// 地图数组

{

{ 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },

{ 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },

{ 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 },

{ 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 },

{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0 },

{ 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 },

{ 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 },

{ 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },

{ 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },

{ 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0 },

{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0 },

{ 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0 },

{ 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0 },

{ 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0 },

{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },

{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },

{ 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0 },

{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0 },

{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0 },

{ 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0 },

{ 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },

{ 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },

{ 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } };

用java编写 深度优先法 寻路时 怎么实现八个方向的路径选择

//循环遍历八个方向：

for(int dx = -1; dx = 1; dx++) {

for(int dy = -1; dy = 1; dy++) {

//向x方向移动dx,向y方向移动dy

int nx = x+dx, ny = y + dy;

if()//这里是你要查找的满足条件的元素

}

}

深度优先和广度优先 的区别 ，用法。

1、主体区别

深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件)。

宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。

2、算法区别

深度优先搜索是每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱，找到所要找的元素时结束程序。

广度优先搜索是每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱，找到所要找的元素时结束程序。

3、用法

广度优先属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

深度优先即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。

扩展资料：

实际应用

BFS在求解最短路径或者最短步数上有很多的应用，应用最多的是在走迷宫上，单独写代码有点泛化，取来自九度1335闯迷宫一例说明，并给出C++/Java的具体实现。

在一个n*n的矩阵里走，从原点（0,0）开始走到终点（n-1,n-1），只能上下左右4个方向走，只能在给定的矩阵里走，求最短步数。n*n是01矩阵，0代表该格子没有障碍，为1表示有障碍物。

int mazeArr[maxn][maxn]; //表示的是01矩阵int stepArr = {{-1,0},{1,0},{0,-1},{0,1}}; //表示上下左右4个方向，int visit[maxn][maxn]; //表示该点是否被访问过，防止回溯，回溯很耗时。核心代码。基本上所有的BFS问题都可以使用类似的代码来解决。

参考资料来源：百度百科-广度优化

参考资料来源：百度百科-深度优化

怎么用java来设计数据结构中的图，图的结点数和边的关系由用户输入，做了好久弄不出来，求解，非常感谢。

是遍历二叉树吗？可以到csdn上去找找，很多类似的东西。看看类似的代码，应该可以编写出来。

别人给你写的，始终是别人的思路。

自己写的，哪怕错了，也要继续写，直到正确。

呵呵，加油亲

java 深度优先搜索（回溯法）求集合的幂集

import java.util.ArrayList;

import java.util.List;

public class BackTrack {

public static void main(String[] args) {

//初始化一个集合，放在list里面

ListString list=new ArrayListString();

list.add("1");

list.add("2");

list.add("3");

list.add("f");

ListString li=new ArrayListString();

PowerSet(0,list,li);

}

//回溯法求幂集

public static void PowerSet(int i,ListString list,ListString li){

if(ilist.size()-1){System.out.println(li);}

else{

li.add(list.get(i));//左加

PowerSet(i+1,list,li); //递归方法

li.remove(list.get(i)); //右去

PowerSet(i+1, list, li);

}

}

}

注：该方法采用中序遍历二叉树（实际这棵树是不存在的）。对于第一个元素，左节点加进去，右节点去掉。对于第i一个节点，左加，右去。直到i大于元素的总个数。

输出结果：

[1, 2, 3, 4]

[1, 2, 3]

[1, 2, 4]

[1, 2]

[1, 3, 4]

[1, 3]

[1, 4]

[1]

[2, 3, 4]

[2, 3]

[2, 4]

[2]

[3, 4]

[3]

[4]

[]

java图深度优先的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于图的深度优先和广度优先、java图深度优先的信息别忘了在本站进行查找喔。