深度优先搜索 java
时间: 2023-11-20 13:59:03 浏览: 44
以下是Java中深度优先搜索的实现方法:
1. 首先,定义一个图类,包含头节点和表节点。
```java
public class Graph {
private HNode[] hNodes; // 头节点数组
public Graph(int size) {
hNodes = new HNode[size];
for (int i = 0; i < size; i++) {
hNodes[i] = new HNode(i);
}
}
// 添加边
public void addEdge(int start, int end) {
TNode tNode = new TNode(end);
tNode.nextArc = hNodes[start].firstArc;
hNodes[start].firstArc = tNode;
}
// 深度优先搜索
public void dfs(int start) {
Stack<Integer> stack = new Stack<>();
stack.push(start);
hNodes[start].isVisit = true;
System.out.print(hNodes[start].data + " ");
while (!stack.isEmpty()) {
int index = stack.peek(); TNode tNode = hNodes[index].firstArc;
boolean isPush = false;
while (tNode != null) {
if (!hNodes[tNode.hNodeIndex].isVisit) {
stack.push(tNode.hNodeIndex);
hNodes[tNode.hNodeIndex].isVisit = true;
System.out.print(hNodes[tNode.hNodeIndex].data + " ");
isPush = true;
break;
}
tNode = tNode.nextArc;
}
if (!isPush) {
stack.pop();
}
}
}
}
```
2. 定义头节点和表节点类。
```java
// 头节点
public class HNode {
public int data; // 数据域
public boolean isVisit; // 标识该头节点是否已经被访问过
public TNode firstArc; // 指针域,指向第一个表节点
public HNode(int data) {
this.data = data;
}
public HNode() {
}
@Override
public String toString() {
return "HNode{" +
"data=" + data +
", isVisit=" + isVisit +
", firstArc=" + firstArc +
'}';
}
}
// 表节点
class TNode {
public int hNodeIndex;// 存储头节点下标
public TNode nextArc; // 指针域,指向下一个相邻的表节点
public TNode(int hNodeIndex) {
this.hNodeIndex = hNodeIndex;
}
}
```
3. 在主函数中创建图对象,添加边,然后进行深度优先搜索。
```java
public static void main(String[] args) {
Graph graph = new Graph(9);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
graph.addEdge(2, 6);
graph.addEdge(3, 7);
graph.addEdge(4, 8);
graph.dfs(0);
}
```
输出结果为:0 1 3 7 4 8 2 5 6。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)