[컴][알고리즘] Depth-First Search DFS, 깊이우선 탐색

개념

각 node 가 visit 을 표시해 놓은 배열이 있다.

모든 node 에서 시작 node 로 간다.
visit 한 node 이면 다음 node 를 살펴본다.

그래서 visit 안한 node 가 있다면,
visit 안한 node 에서 시작한다.
이 node 가 start vertex 가 된다.

그러면 이 node 에서 어떤 일을 하냐면
이 node 에 붙어있는 node 들을 하나씩 보면서,
visit 안한 녀석을 찾으면
그 visit 안한 녀석을 다시 파고들어간다.

그 visit 안한 녀석을 잡고
다시, 그 node 에 붙어있는 node 들을 하나씩 보고,
visit 안한 녀석을 찾는다.

그렇게 가다보면, 결국 visit 안한 녀석을 찾을 수 없게 되고,
그러면 다시 visit 안한 녀석을 찾을 수 있는 depth 까지 돌아오게 된다.
그리고는 다시 또 쭉 파고 들어간다.

아래 예제에서는 이 visit 을 표시하는 부분과 parent 를 설정하는 부분을 python dictionary 를 이용해서 동시에 하고 있다.
parent[v] 를 통해서 parent 를 저장하고,
동시에 parent[v] 가 없다면, 아직 visit 을 안한 것으로 파악할 수 있다.

source

• dfs_visit : visit한 vertex 를 시작점으로하고, visit 하지않은 adjVertex 를 visit 한다.

parent = {}

def dfs(vertices, adj):

    for s in vertices:  
        if s not in parent:
            parent[s] = None    # v is start vertex
            dfs_visit(vertices, adj, s)

def dfs_visit(vertices, adj, start):
    for v in adj[start]:
        if v not in parent: # not in parent means node is not visited
            parent[v] = start
            dfs_visit(vertices, adj, v)

Source from : 14. Depth-First Search (DFS), Topological Sort, MIT Open Open Course Ware

vertices

visit 해야 할 모든 vertex 들이다.

adj

한 vertex 에 연결되어 있는 vertex 들

adj[0] =[1,2,3] 

이라고 한다면, 0 에 1, 2, 3 이 연결되어 있는 것이다.(adjacent nodes)

parent

여기서 parent 는 parent 를 설정하는 역할도 하지만, 동시에 지나온 경로 path 를 알려주기도 한다. 물론 지나온 경로를 순차적으로 알기 위해서는 다른 변수를 써서 저장해야 하지만, 방문했는지 여부는 parent 로 파악할 수 있다.

dfs()

dfs_visit() 이 실제로 dfs 이며, dfs 부분은 연결되어 있지 않은 vertex 를 visit 하게 해준다. 아래와 같은 graph 를 모두 traverse 하게 해 준다.

iterative version

dfs 의 iterative 버전에 대한 설명은 여기에 해 놨는데, iterative 부분은 recursive 보다 이해하기 힘들 수도 있다.