자료구조 - 그래프(GRAPH)

정의

- 어떤 자료나 개념을 표현하는 정점(VERTEX)들의 집합 V와 이들을 연결하는 간선(EDGE)들의 집합 E로 구성된 자료구조

- 트리는 계층구조로 한방향(위에서 아래로)으로만 연결되지만 그래프는 제약없이 연결된다.

- 위와 같은 이유로 모든 트리는 그래프라고 할 수 있으나 모든 그래프는 트리라고 할 수없다.

 

종류

- 방향 그래프 VS 무향 그래프(코테에 가장 많이 나옴)

    간선에 방향성이 있는지(방향 그래프)  없는지(무향 그래프) 

- 다중 그래프 VS 단순 그래프

    정점과 정점이 연결될 때 간선이 하나인지(단순 그래프) 여러개인지(다중그래프) 

- 가중치 그래프 => 다익스트라

    간선에 수치로 가중치가 있다.

 

구현방법

- 인접리스트(adjacency list)

- 인접행렬(adjacency matrix)

- 암시적 그래프(implicit graph)

 

#인접행렬
graph = [
    [0, 0, 1, 0, 1], # 1번 노드는 3,5와 연결됨
    [0, 0, 0, 1, 1], # 2번 노드는 4,5와 연결됨
    [1, 0, 0, 0, 1], # 3번 노드는 1,5와 연결됨
    [0, 1, 0, 0, 1], # 4번 노드는 2,5와 연결됨
    [1, 1, 1, 1, 1]  # 5번 노드는 1,2,3,4,5와 연결됨
] 

#인접리스트
graph = [
    1: [3,5],
    2: [4,5],
    3: [1,5],
    4: [2,5],
    5: [1,2,3,4]
] 

#보통 인접행렬보다 인접리스트가 메모리 공간을 적게 차지함으로 인접리스트 추천

#암시적 그래프
graph = [
    [1, 1, 1, 1, 1], #(0,0), (0,1), (0,2), (0,3), (0,4)
    [0, 0, 0, 1, 1], #(1,0), (1,1), (1,2), (1,3), (1,4)
    [1, 1, 0, 1, 1], #(2,0), (2,1), (2,2), (2,3), (2,4)
    [1, 0, 0, 0, 0], #(3,0), (3,1), (3,2), (3,3), (3,4)
    [1, 1, 1, 1, 1]  #(4,0), (4,1), (4,2), (4,3), (4,4)
]

그래프 순회

- 그래프 탐색이라고도 하며 그래프의 각 정점을 방문하는 과정을 말한다. 

- 깊이우선탐색(DFS), 너비우선탐색(BFS)

 

 

출저) https://www.inflearn.com/course/lecture?courseSlug=%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%85%EB%AC%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC&unitId=138423&tab=curriculum 

학습 페이지