深度优先遍历java代码 深度优先遍历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中解析xml有哪几种方法

(1)DOM解析

DOM是html和xml的应用程序接口(API)，以层次结构（类似于树型）来组织节点和信息片段，映射XML文档的结构，允许获取

和操作文档的任意部分，是W3C的官方标准

【优点】

①允许应用程序对数据和结构做出更改。

②访问是双向的，可以在任何时候在树中上下导航，获取和操作任意部分的数据。

【缺点】

①通常需要加载整个XML文档来构造层次结构，消耗资源大。

【解析详解】

①构建Document对象：

DocumentBuilderFactory dbf = DocumentBuilderFactory.newInstance();

DocumentBuilder db = bdf.newDocumentBuilder();

InputStream is = Thread.currentThread().getContextClassLoader().getResourceAsStream(xml文件);

Document doc = bd.parse(is);

②遍历DOM对象

Document： XML文档对象，由解析器获取

NodeList： 节点数组

Node： 节点(包括element、#text)

Element： 元素，可用于获取属性参数

(2)SAX(Simple API for XML)解析

流模型中的"推"模型分析方式。通过事件驱动，每发现一个节点就引发一个事件，事件推给事件处理器，通过回调方法

完成解析工作，解析XML文档的逻辑需要应用程序完成

【优势】

①不需要等待所有数据都被处理，分析就能立即开始。

②只在读取数据时检查数据，不需要保存在内存中。

③可以在某个条件得到满足时停止解析，不必解析整个文档。

④效率和性能较高，能解析大于系统内存的文档。

【缺点】

①需要应用程序自己负责TAG的处理逻辑（例如维护父/子关系等），文档越复杂程序就越复杂。

②单向导航，无法定位文档层次，很难同时访问同一文档的不同部分数据，不支持XPath。

【原理】

简单的说就是对文档进行顺序扫描，当扫描到文档(document)开始与结束、元素(element)开始与结束时通知事件

处理函数(回调函数)，进行相应处理，直到文档结束

【事件处理器类型】

①访问XML DTD：DTDHandler

②低级访问解析错误：ErrorHandler

③访问文档内容：ContextHandler

【DefaultHandler类】

SAX事件处理程序的默认基类，实现了DTDHandler、ErrorHandler、ContextHandler和EntityResolver接口，通常

做法是，继承该基类，重写需要的方法，如startDocument()

【创建SAX解析器】

SAXParserFactory saxf = SAXParserFactory.newInstance();

SAXParser sax = saxf.newSAXParser();

注：关于遍历

①深度优先遍历(Depthi-First Traserval)

②广度优先遍历(Width-First Traserval)

(3)JDOM(Java-based Document Object Model)

Java特定的文档对象模型。自身不包含解析器，使用SAX

【优点】

①使用具体类而不是接口，简化了DOM的API。

②大量使用了Java集合类，方便了Java开发人员。

【缺点】

①没有较好的灵活性。

②性能较差。

(4)DOM4J(Document Object Model for Java)

简单易用，采用Java集合框架，并完全支持DOM、SAX和JAXP

【优点】

①大量使用了Java集合类，方便Java开发人员，同时提供一些提高性能的替代方法。

②支持XPath。

③有很好的性能。

【缺点】

①大量使用了接口，API较为复杂。

(5)StAX(Streaming API for XML)

流模型中的拉模型分析方式。提供基于指针和基于迭代器两种方式的支持,JDK1.6新特性

【和推式解析相比的优点】

①在拉式解析中，事件是由解析应用产生的，因此拉式解析中向客户端提供的是解析规则，而不是解析器。

②同推式解析相比，拉式解析的代码更简单，而且不用那么多库。

③拉式解析客户端能够一次读取多个XML文件。

④拉式解析允许你过滤XML文件和跳过解析事件。

【简介】

StAX API的实现是使用了Java Web服务开发（JWSDP）1.6，并结合了Sun Java流式XML分析器(SJSXP)-它位于

javax.xml.stream包中。XMLStreamReader接口用于分析一个XML文档，而XMLStreamWriter接口用于生成一个

XML文档。XMLEventReader负责使用一个对象事件迭代子分析XML事件-这与XMLStreamReader所使用的光标机制

形成对照。

用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代码的满足条件深度优先遍历java代码的元素

}

}

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