深度优先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 深度优先搜索(回溯法)求集合的幂集
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编写 深度优先法 寻路时 怎么实现八个方向的路径选择
//循环遍历八个方向:
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()//这里是你要查找的满足条件的元素
}
}
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代码 深度优先使用什么数据结构
转载注明:http://myzitong.com/article/dddeico.html