13. 图-DFS (递归)

正文

class Graph {
    private val adjList: MutableMap<Int, MutableList<Int>> = mutableMapOf()

    fun addEdge(u: Int, v: Int) {
        adjList.getOrPut(u) { mutableListOf() }.add(v)
    }

    fun dfs(vertex: Int) {
        val visited = mutableSetOf<Int>()
        dfsHelper(vertex, visited)
    }

    private fun dfsHelper(vertex: Int, visited: MutableSet<Int>) {
        visited.add(vertex)
        println(vertex) // 在这里可以对当前节点进行相关操作

        val neighbors = adjList[vertex]
        if (neighbors != null) {
            for (neighbor in neighbors) {
                if (!visited.contains(neighbor)) {
                    dfsHelper(neighbor, visited)
                }
            }
        }
    }
}

fun main() {
    val graph = Graph()
    // 添加图的边
    graph.addEdge(0, 1)
    graph.addEdge(0, 2)
    graph.addEdge(1, 3)
    graph.addEdge(2, 4)
    graph.addEdge(3, 4)

    // 从节点 0 开始进行深度优先搜索
    graph.dfs(0)
}