내멋대로 자료구조 - 그래프, DFS, BFS

1. 그래프란?

- 자료구조 중 연결되어 있는 정점(Vertex, Node)과 정점간의 관계(Edge)를 표현할 수 있는 자료구조

- 그래프는 유방향(Directed)과 무방향(Undirected)로 이루어진다

 

2. 그래프를 표현하는 방법

- 인접 행렬 (Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현

GOOD : 연결여부를 바로 알 수 있다.

BAD : 모든 조합의 연결여부를 저장해야 하기 때문에 O(n^2)

- 인접 리스트(Adjacency List): 링크드 리스트로 그래프의 연결 관계를 표현

GOOD : 모든 조합의 연결여부를 저장할 필요 X. O(노드+간선)만큼의 공간 사용

BAD : 각 리스트를 돌아야 연결되었는지 여부가 정확하게 알 수 있음

 

3. DFS (Depth First Search - 깊이 우선 탐색)

갈 수 있는 만큼 계속해서 탐색 후 안돼면 다른 방향으로 다시 탐색하는 구조

DFS로 방문시 [1,2,5,6,7,3,4]

DFS를 풀어가는 방법은 크게 두 가지로 나뉘어져 있다.

1) 재귀함수 : 재귀 함수의 경우 방문처리 후 계속 말단 노드까지 재귀함수를 호출하여 더 이상 방문할 지점이 없을 때 상위 레벨로가서 또 재귀를 반복하여 최종으로 그래프를 다 탐색할 때까지 반복하는 로직으로 되어 있다.

따라서 재귀함수로 DFS를 구현 시, 탈출 조건을 꼭 함수 첫 부분에 작성해야 무한루프를 타지 않을 수 있다.

2) 스택 : 스택에 먼저 탐색을 할 스타팅 노드(루트노드)를 넣어주고, 스택이 차면 정점 하나를 꺼내서 방문처리를 한 후 해당 정점에 인접한 모든 정점을 스택에 넣고 또 팝해서 노드를 타고 다니는 식으로 

# dfs 재귀함수
def dfs_recursive(node, visited):
    # 방문처리
    visited.append(node)

    # 인접 노드 방문, 방문하지 않았으면 다시 재귀 함수 호출
    for adj in graph[node]:
        if adj not in visited:
            dfs_recursive(adj, visited)

    return visited


# dfs 스택
def dfs_stack(start):
	# 방문처리용 빈 배열
    visited = []
    # 방문할 순서를 담아두는 용도
    stack = [start]

    # 방문할 노드가 남아있는 한 아래 로직을 반복한다.
    while stack:
        # 제일 최근에 삽입된 노드를 꺼내고 방문처리한다.
        top = stack.pop()
        visited.append(top)
        # 인접 노드를 방문한다.
        for adj in graph[top]:
            if adj not in visited:
            	# 인접노드를 방문 후 방문하지 않은 노드일 경우 스택에 다시 삽입
                stack.append(adj)

    return visited

 

4. BFS (Breadth First Search - 너비 우선 탐색)

BFS로 방문시 [1,2,3,4,5,6,7]

BFS는 말 그대로 루트에서 인접한 노드를 먼저 방문해야 한다. 그 말인 즉슨 들어 온 순서대로 방문을 해야 한다는 의미이므로 큐를 이용하면 BFS를 구현 가능하다. (큐에 들어온 순서대로 방문 후 인접 노드를 큐에 추가하고 방문처리)

def bfs_queue(start):
	# 루트 노드 방문처리
    visited = [start]
    # 데큐에 루트노드를 집어넘
    q = deque([start])

	# 큐가 있을 때
    while q:
    	# 큐를 뽑아서 노드에 넣는다
        node = q.popleft()
        # 인접노드를 방문하며, 방문하지 않았다면 해당 노드를 큐에 넣고, 방문처리 한다
        for adj in graph[node]:
            if adj not in visited:
                q.append(adj)
                visited.append(adj)

    return visited