dfs bfs

dfs

 
 
fun dfs(graph:MutableList<MutableList<Int>>,v:Int, visited:MutableList<Boolean>){
    visited[v] = true
    print("$v ")
    for(i in graph[v]){
        if(!(visited[i])){
            dfs(graph, i ,visited)
        }
    }
}
fun main(){
    // mutableListOf<Int>()는 빈 리스트를 생성하기 때문에 제너릭을 써야함
    val graph = mutableListOf(
        mutableListOf<Int>(),
        mutableListOf(2,3,8),
        mutableListOf(1,7),
        mutableListOf(1,4,5),
        mutableListOf(3,5),
        mutableListOf(3,4),
        mutableListOf(7),
        mutableListOf(2,6,8),
        mutableListOf(1,7),
    )
    val visited = MutableList(9,{false})
 
    dfs(graph, 1, visited) //1 2 7 6 8 3 4 5
}

 

import java.util.*
 
fun bfs(graph:MutableList<MutableList<Int>>,v:Int, visited:MutableList<Boolean>){
    var q : Queue<Int> = LinkedList<Int>()
    q.add(v)
 
    visited[v] = true
    while(!q.isEmpty()){
        var a = q.poll()
        print("$a ")
        for(i in graph[a]){
            if(!visited[i]){
                q.add(i)
                visited[i]=true
            }
        }
 
    }
}
fun main(){
    // mutableListOf<Int>()는 빈 리스트를 생성하기 때문에 제너릭을 써야함
    val graph = mutableListOf(
        mutableListOf<Int>(),
        mutableListOf(2,3,8),
        mutableListOf(1,7),
        mutableListOf(1,4,5),
        mutableListOf(3,5),
        mutableListOf(3,4),
        mutableListOf(7),
        mutableListOf(2,6,8),
        mutableListOf(1,7),
    )
    val visited = MutableList(9,{false})
 
    bfs(graph, 1, visited) //1 2 3 8 7 4 5 6 
}