DFS

목적 : 한 정점에서 시작해서 연결된 모든 정점을 한 번씩 방문하는 것

 

DFS의 경우 재귀호출을 통해서 구현하도록 한다.

 

인접행렬 버전

이때, DFS의 x호출은 x를 방문했다는 것이다. 따라서 방문 표시를 해 주고, 이제 그 다음 정점을 찾아야 한다.

• 그 다음 정점은 x에서 i사이의 간선이 있어야 한다.
• i를 방문한적이 없음

위 2가지 조건을 만족해야지 이동할 수 있다. 이때 시간 복잡도는 O(V^2)이다.

def dfs(int x):
    check[x] = True
    for i in range(1,n+1):
        if a[x][i] == 1 and check[i] == False:
            dfs(i)

 

인접리스트를 사용할 경우, x에서 i를 찾는 방법만 변경해주면 된다. 인접리스트에서 a[x]에 들어있는 것은 x와 연결된 모든 정점 즉, 간선이다. 따라서 항상 연결되어 있는 경우만 찾으면 되는 방식으로 구현하면 되고, 이동한 적이 있는지 없는지만 파악해주면 된다. 시간복잡도는 for loop안에서 x와 연결되어 있는 횟수이기 때문에, O(V+E)라고 계산할 수 있다.

def dfs(int x):
    check[x] = True
    for y in a[x]:
        if check[y] == False:
            dfs(y)