hello-algo/codes/java/chapter_graph/graph_dfs.java

51 lines
1.8 KiB
Java
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

/**
* File: graph_dfs.java
* Created Time: 2023-02-12
* Author: krahets (krahets@163.com)
*/
package chapter_graph;
import java.util.*;
import utils.*;
public class graph_dfs {
/* 深度优先遍历辅助函数 */
static void dfs(GraphAdjList graph, Set<Vertex> visited, List<Vertex> res, Vertex vet) {
res.add(vet); // 记录访问顶点
visited.add(vet); // 标记该顶点已被访问
// 遍历该顶点的所有邻接顶点
for (Vertex adjVet : graph.adjList.get(vet)) {
if (visited.contains(adjVet))
continue; // 跳过已被访问的顶点
// 递归访问邻接顶点
dfs(graph, visited, res, adjVet);
}
}
/* 深度优先遍历 */
// 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
static List<Vertex> graphDFS(GraphAdjList graph, Vertex startVet) {
// 顶点遍历序列
List<Vertex> res = new ArrayList<>();
// 哈希集合,用于记录已被访问过的顶点
Set<Vertex> visited = new HashSet<>();
dfs(graph, visited, res, startVet);
return res;
}
public static void main(String[] args) {
/* 初始化无向图 */
Vertex[] v = Vertex.valsToVets(new int[] { 0, 1, 2, 3, 4, 5, 6 });
Vertex[][] edges = { { v[0], v[1] }, { v[0], v[3] }, { v[1], v[2] },
{ v[2], v[5] }, { v[4], v[5] }, { v[5], v[6] } };
GraphAdjList graph = new GraphAdjList(edges);
System.out.println("\n初始化后图为");
graph.print();
/* 深度优先遍历 */
List<Vertex> res = graphDFS(graph, v[0]);
System.out.println("\n深度优先遍历DFS顶点序列为");
System.out.println(Vertex.vetsToVals(res));
}
}