使用Java函数实现图的深度优先搜索(DFS)和广度优先搜索(BFS)。
发布时间:2023-07-02 09:19:32
深度优先搜索(DFS)和广度优先搜索(BFS)都是图的遍历算法,用于遍历图中的节点。下面是使用Java函数实现DFS和BFS的示例代码。
深度优先搜索(DFS):
import java.util.*;
// 图的节点类
class Node {
int value;
List<Node> neighbors;
public Node(int value) {
this.value = value;
this.neighbors = new ArrayList<>();
}
}
public class DFS {
// DFS遍历函数
public static void dfs(Node node, Set<Node> visited) {
System.out.print(node.value + " ");
visited.add(node);
for (Node neighbor : node.neighbors) {
if (!visited.contains(neighbor)) {
dfs(neighbor, visited);
}
}
}
public static void main(String[] args) {
// 创建图
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
// 构建图的关系
node1.neighbors.add(node2);
node1.neighbors.add(node3);
node2.neighbors.add(node4);
// 创建访问集合
Set<Node> visited = new HashSet<>();
// 调用DFS函数
dfs(node1, visited);
}
}
输出结果:1 2 4 3
广度优先搜索(BFS):
import java.util.*;
// 图的节点类
class Node {
int value;
List<Node> neighbors;
public Node(int value) {
this.value = value;
this.neighbors = new ArrayList<>();
}
}
public class BFS {
// BFS遍历函数
public static void bfs(Node node) {
Queue<Node> queue = new LinkedList<>();
Set<Node> visited = new HashSet<>();
queue.offer(node);
visited.add(node);
while (!queue.isEmpty()) {
Node currentNode = queue.poll();
System.out.print(currentNode.value + " ");
for (Node neighbor : currentNode.neighbors) {
if (!visited.contains(neighbor)) {
queue.offer(neighbor);
visited.add(neighbor);
}
}
}
}
public static void main(String[] args) {
// 创建图
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
// 构建图的关系
node1.neighbors.add(node2);
node1.neighbors.add(node3);
node2.neighbors.add(node4);
// 调用BFS函数
bfs(node1);
}
}
输出结果:1 2 3 4
以上是DFS和BFS的简单实现示例,通过创建图的节点对象和建立节点之间的连接关系,然后使用DFS和BFS函数进行遍历。在遍历过程中使用Set集合来记录访问过的节点,保证节点不会被重复访问。
