DFS

참고한 영상
DFS 위키백과
깊이 우선 탐색(Depth-First Search)
최대한 깊은 단계까지 우선 검색하는 방법.

구현방법으론 스택과 재귀식 구현이 있음.

• 장점
  • 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.
  • 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
• 단점
  • 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다.
  • 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

영상 보면서 직접 코틀린으로 구현해본 소스 코드.

import java.util.*

class Graph(val size : Int = 10) {
    val nodes: Array<Node> = Array<Node>(10, { i -> (Node(i))})

    class Node(var data : Int = 0, var adjacent : LinkedList<Node> = LinkedList(), var marked : Boolean = false)
    fun addEdge(original : Int, adjacent : Int) {       //인접 노드 설정하는 메소드.
        val node1 = nodes[original]
        val node2 = nodes[adjacent]

        if (!node1.adjacent.contains(node2)) {
            node1.adjacent.add(node2)
        }
        if (!node2.adjacent.contains(node1)) {
            node2.adjacent.add(node1)
        }
    }
    fun dfs() {
        dfs(0)
    }
    fun dfs(index : Int) {
        val root : Node = nodes[index]
        val stack : Stack<Node> = Stack<Node>()
        stack.push(root)
        root.marked = true
        while(!stack.empty()) {
            val r : Node = stack.pop()
            for (n : Node in r.adjacent) {
                if (n.marked == false) {
                    n.marked = true
                    stack.push(n)
                }
            }
            println(r.data)
        }
    }
}

fun main() {
    val graph : Graph = Graph(10)
    graph.addEdge(0,1)
    graph.addEdge(1,3)
    graph.addEdge(1,4)
    graph.addEdge(3,7)
    graph.addEdge(3,8)
    graph.addEdge(4,9)
    graph.addEdge(0,2)
    graph.addEdge(2,5)
    graph.addEdge(2,6)
    graph.dfs()
}

//출력 결과
0
2
6
5
1
4
9
3
8
7