[알고리즘] 03. 그래프 탐색 - 1

in Computer-Science

다양한 그래프 탐색 알고리즘의 특징을 살펴본다.

그래프의 의미

그래프는 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node) 와 간선(Edge)로 표현하기 위해 사용

  • 노드 (Node): 위치를 말함, 정점(Vertex)라고도 함

  • 간선 (Edge): 위치 간의 관계를 표시한 선으로 노드를 연결한 선이라고 보면 됨 (link 또는 branch 라고도 함)

  • 인접 정점 (Adjacent Vertex) : 간선으로 직접 연결된 정점(또는 노드)

1. 너비 우선 탐색(BFS)

def bfs(st_node, graph):
    v = [st_node]
    nv = graph[st_node]
    while len(v) != len(graph.keys()) or nv != []:
        tmp = nv.pop(0)
        if tmp not in v:
            v.append(tmp)
            nv.extend(graph[tmp])
    return v

왼쪽 그림처럼 depth의 모든 노드를 탐색하고 그 다음 depth로 이동하여 노드를 탐색한다.

2. 깊이 우선 탐색(DFS)

def dfs(st_node, graph):
    v = [st_node]
    nv = graph[st_node]
    while len(v) != len(graph.keys()) or nv != []:
        tmp = nv.pop(-1)
        if tmp not in v:
            v.append(tmp)
            nv.extend(graph[tmp])
    return v

  1. 오른쪽 그림처럼 연결된 노드를 depth 순서대로 탐색한다.

  2. 그 다음 depth의 노드가 없을 경우 해당 depth의 다른 노드를 탐색하고 1의 과정을 반복한다.

  3. 2의 과정에서 다른 노드가 없을 경우 이전 depth로 가서 2의과정을 반복한다.

  4. 1~3의 과정을 반복하여 원하는 값을 탐색한다.

3. 시간 복잡도

  • 노드 수 : V

  • 간선 수 : E

  • 시간복잡도 : O(V + E)

이미지 출처 : 잔재미 코딩

© 2020. All rights reserved.