알고리즘 공부/bfs,dfs
dfs bfs
_우지
2021. 7. 14. 17:03
dfs
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
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
}
|
cs |
BFS도 DFS와 같은 그래프를 사용합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
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
}
|
cs |