14. 图-DFS (迭代)

正文

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

    fun addEdge(u: Int, v: Int) {
        adjacencyList.computeIfAbsent(u) { mutableListOf() }.add(v)
    }

    fun dfs(start: Int) {
        val visited = mutableSetOf<Int>()
        val stack = mutableListOf<Int>()

        stack.add(start)
        while (stack.isNotEmpty()) {
            val vertex = stack.removeAt(stack.size - 1)
            if (!visited.contains(vertex)) {
                visited.add(vertex)
                println("Visited vertex: $vertex")

                adjacencyList[vertex]?.reversed()?.forEach { neighbor ->
                    if (!visited.contains(neighbor)) {
                        stack.add(neighbor)
                    }
                }
            }
        }
    }
}

fun main() {
    val graph = Graph()

    // 添加图的边
    graph.addEdge(0, 1)
    graph.addEdge(0, 2)
    graph.addEdge(1, 3)
    graph.addEdge(1, 4)
    graph.addEdge(2, 5)
    graph.addEdge(2, 6)

    // 从顶点0开始进行DFS
    graph.dfs(0)
}