DataStructure [Graph]

그래프란?📖

정점(vertex, Node)과 정점 사이를 연결하는 간선(edge)으로 이루어진 비선형 자료구조.

✏️그래프의 종류

무방향 그래프(Undirected Graph)

• 서로 연결된 정점 사이에는 어떤 상하 관계나 순서가 존재하지 않는다.

방향 그래프(Directed Graph)

• 각 간선이 방향을 가지며, 한 정점에서 다른 정점으로의 방향이 정의되어 있다.

가중치 그래프(Weighted Graph)

• 간선(Edge)에 "가중치" 또는 "비중"을 할당한 그래프로, 간선이나 경로 사이의 관계나 거리를 나타내는데 사용된다.

✏️그래프 순회 (Graph Traversals)

그래프 자료 구조를 탐색하거나 검색하는 과정.

그래프 순회에는 크게 깊이 우선 탐색 (Depth - First Search: DFS)과 너비 우선 탐색 (Breadth - First Search: BFS)의 2가지 알고리즘이 있다.

DFS (깊이 우선 탐색)

현재 정점에서 연결된 정점을 하나 골라 파고들수 있는 최대한 깊게 파고들어가며 탐색하는 방법이다.

• 스택 (stack)또는 재귀를 이용
  
  

예시

다음 그래프를 인접 리스트를 이용하여 표현하면 다음과 같다.

graph = {
    0: [1, 2, 3],
    1: [5, 6],
    2: [4],
    3: [2, 4],
    4: [1],
    5: [],
    6: [4]
}

def recursive_dfs(v, discovered=[]):
    discovered.append(v)
    for w in graph[v]:
        if w not in discovered:
            discovered = recursive_dfs(w, discovered)
    return discovered

print(recursive_dfs(0))

출력
[0, 1, 5, 6, 4, 2, 3]

BFS (너비 우선 탐색)

현재 정점과 연결된 정점들에 대해 우선적으로 넓게 탐색하는 방법이다.

• 큐 (queue)를 이용

from collections import deque
queue = deque()

graph = {
    0: [1, 2, 3],
    1: [5, 6],
    2: [4],
    3: [2, 4],
    4: [1],
    5: [],
    6: [4]
}

def bfs(start):
    discovered = [start]
    queue.append(start)
    while queue:
        v = queue.popleft()
        for w in graph[v]:
            if w not in discovered:
                discovered.append(w)
                queue.append(w)
    return discovered

print(bfs(0))

출력
[0, 1, 2, 3, 5, 6, 4]