Graph + DFS

그래프 순회를 할 때 2가지 방법이 있다. BFS가 있고, DFS가 있다. 

트리 순회를 할 때에도 BFS로 할 수도 있고, DFS로 할 수도 있다.

BFS가 옆으로 가는 느낌이라면,

DFS는 밑으로 끝까지 쭉 가서 단말노드에 닿을 때까지 가는 느낌이다. 

 

DFS를 미로찾기로 이해하면 쉽다. 

막다른 곳으로 가더라도 쭉 간 다음에 아니면 돌아오고 (백트래킹), 

또 쭉 가보고 하다가 도착 지점에 짠하고 도착할 수 있다. 

 

파이썬에서 DFS를 구현하려면 stack이라는 자료 구조를 써야 한다.

스택을 통해서 방문한 노드를 저장하는 것이다. 스택은 last in first out (LIFO)이다.

루트 노드로 시작해서 루트 노드를 pop 한 다음에 루트 노드와 연결된 모든 노드들을 스택에 넣는다.

스택이 empty 될 때까지 반복한다.

 

새로운 노드에 도착할 때마다 다음의 과정을 반복한다.

(1) 스택에 노드를 집어넣는다.

(2) 방문 처리한다.

(3) 이 노드가 인접 노드가 있는지를 체크한다. 인접노드가 있는데 방문한 적이 없다면 방문한다. 인접노드가 없으면 스택에서 제거한다. 

 

def dfs(node, graph, visited, component):
    component.append(node)  # Store answer
    visited[node] = True  # Mark visited

    # Traverse to each adjacent node of a node
    for child in graph[node]:
        if not visited[child]:  # Check whether the node is visited or not
            dfs(child, graph, visited, component)  # Call the dfs recursively


if __name__ == "__main__":

    # Graph of nodes
    graph = {
        0: [2],
        1: [2, 3],
        2: [0, 1, 4],
        3: [1, 4],
        4: [2, 3]
    }
    node = 0  # Starting node
    visited = [False]*len(graph)  # Make all nodes to False initially
    component = []
    dfs(node, graph, visited, component)  # Traverse to each node of a graph
    print(f"Following is the Depth-first search: {component}")  # Print the answer

 

 

복잡도

(1) 시간 복잡도

directed graph: O(V + |E|) where V is number of vertices and E is number of edges

undirected graph: O(V + 2 * |E|) because each edge is visited twice

 

트리에서의 DFS는 O(V)이고, V는 노드의 개수이다.

 

(2) 공간 복잡도: O(V) (V는 노드의 개수이다)

 

 

참고

https://www.scaler.com/topics/dfs-python/