Graph(1)

그래프란

그래프(G)는 노드(정점, Vertex)들의 집합 V와 이들을 연결하는 간선(Edge)들의 집합 E로 구성된 자료구조입니다. 쉽게말해, 그래프는 노드와 간선으로 이루어진 자료구조이다.

그래프의 종류

• 무향 그래프(undirected graph): 방향이 정해져있지 않은 양방향 그래프를 의미합니다. ❗️코딩테스트에서 주로 많이 다룬다.
• 방향 그래프(directed graph): 방향이 정해져 있는 그래프로 단뱡향 그래프를 의미합니다. 즉, 아래 사진과 같이 방향이 정해진 그래프 입니다. 그래프를 살펴보면 들어오는 간선과 나가는 간선이 있는데, 들어오는 간선을 indgree라 하며, 나가는 간선을 outdgree라 합니다. 예를들어, 아래 노드 B는 노드 A와 C로 부터 들어오고 E로 나가기 때문에 indegree=2, outdegree=1 이다.

• 다중 그래프: 노드와 노드사이의 간선이 여러개인 경우를 의미한다. 즉, 들어오는 간선과 나가는 간선이 각각 1개를 초과하는 그래프

• 단순 그래프: 노드와 노드사이에 들어오는 간선과 나가는 간선이 각각 1개씩인 경우의 그래프를 의미한다. ❗️코드 테스트에서 주로 다룬다.

• 가중치 그래프: 노드와 노드를 연결하는 간선의 비용이 각각 다르다. 모든 경로의 비용이 같은 경우도 있으나 경로마다 비용이 다른 상황을 가중치가 다르다하여 이러한 그래프를 가중치 그래프라고 합니다. ❗️다익스트라 알고리즘에서 주로 사용됩니다,

그래프의 구현

• 인접 행렬: 그래프를 행(row)과 열(column)에따라, 정보들을 직사각형 모양으로 배열한 것.

matrix = [
    [0, 1, 0, 0, 0, 0],
    [1, 0, 1, 0, 1, 0],
    [0, 1, 0, 1, 0, 0],
    [0, 0, 1, 0, 1, 1],
    [0, 1, 0, 1, 0, 1],
    [0, 0, 0, 1, 1, 0],
]

• 인접 리스트: 딕셔너리 {} 형태로 정의됩니다. 딕셔너리는 key와 value로 정의되는 자료구조로 인접 리스트 같은 경우는 key에는 정점이 들어가고 value에는 key와 연결된 노드들의 연결 관계를 표시해 준다. ❗️코딩테스트에서 인접 행렬방식보다는 주로 인접 리스트 방식을 사용한다. why? 메모리 사용이 더 효율적

graph = {
    "A": ["B"],
    "B": ["A", "C", "E"],
    "C": ["B", "D"],
    "D": ["C", "E", "F"],
    "E": ["B", "D", "F"],
    "F": ["D", "E"],
}

• 암시적 그래프: ❗️코딩테스트에서 자주 다루게 될 그래프 암시적 그래프. 코딩 테스트를 풀다보면 다음과 같은 문제들을 자주 접하게 된다.

위 사진은 전혀 그래프 처럼 보이지 않지만 암시적으로 그래프 처럼 표현할 수 있습니다. 

예를들어, 벽에는 '1'의 값을, 길에는 '0'의 값을 넣음으로써 구분할 수 있다. 그리고 각 영역을 좌표의 개념을 도입하여 표현할 수 있다.

graph = [
    [1, 1, 1, 1, 1],
    [0, 0, 0, 1, 1],
    [1, 1, 0, 1, 1],
    [1, 0, 0, 0, 0],
    [1, 1, 1, 1, 1],
]

위 표현 방식은, 각 노드마다의 연결 관계를 명확하게 나타내지는 않지만 암시적으로 각 노드마다 상 하 좌 우로 연결되어 있음을 알 수 있다. 따라서 가로를 row 세로를 column으로 생각함으로써 graph[row][column]를 통해 원하는 값으로 접근할 수 있습니다. 예를들어 (2,3)을 알고 싶다면 graph[2][3]을 통해 값이 '1=벽' 임을 알 수 있습니다.