[자료구조/알고리즘] 비선형 구조 | 그래프(Graph)

Eunji Lee·2023년 1월 21일
0

의미


(출처: Graph Data Structure And Algorithms)

여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조


구조

  • 하나의 점을 정점(vertex), 하나의 선은 간선(edge) 이라고 부름
  • 직접적인 관계라면 두 정점 사이를 이어주는 간선이 있음
  • 간접적인 관계라면 몇 개의 정점과 간선에 걸쳐 이어짐

용어

  • 정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소
  • 간선 (edge): 정점을 이어주는 선으로 정점 간의 관계를 나타냄

  • 인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점임
  • 인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점

  • 가중치 그래프 (weighted Graph): 연결의 강도(추가적인 정보, ex. 서울-부산으로 가는 거리 등)가 얼마나 되는지 적혀져 있는 그래프
  • 비가중치 그래프 (Unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프

  • 무(방)향 그래프 (Undirected Graph): 방향이 정해지지 않은 간선을 가진 그래프
    • ex. 네비게이션: 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는 것도 가능
  • 단방향 그래프(directed Graph): 방향이 정해진 간선을 가진 그래프
    • ex. 서울과 부산이 일방통행 도로로 이어진 경우: 서울에서 부산을 갈 수 있지만, 부산에서 서울로 가는 것은 불가능(혹은 그 반대)

  • 진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냄
  • 자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우로, 다른 정점을 거치지 않음
  • 사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있는 경우
    • ex. 내비게이션 그래프: 서울 —> 대전 —> 부산 —> 서울 로 이동 가능하므로 사이클 있음

표현 방식

인접 행렬(Adjacency Matrix)


(출처: Adjacency Matrix)

  • 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타냄
  • 만약 A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시함
  • 만약 가중치 그래프라면 1 대신 관계에서 의미 있는 값을 저장
  • 활용
    • 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이
      • 예를 들어, A에서 B로 진출하는 간선이 있는지 파악하기 위해선 0 번째 줄의 1 번째 열에 어떤 값이 저장되어있는지 바로 확인할 수 있음
    • 가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용

인접 리스트(Adjacency List)


(출처: Graph Representation: Edge list, Adjacency Matrix, and Adjacency lists)

  • 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현
  • 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있음
  • 그래프를 인접 리스트로 구현할 때, 정점별로 살펴봐야 할 우선 순위를 고려해 구현할 수 있으며, 리스트에 담겨진 정점들을 우선 순위별로 정렬할 수 있음
  • 우선 순위가 없다면, 연결된 정점들을 단순하게 나열한 리스트가 됨
  • 활용
    • 메모리를 효율적으로 사용하고 싶을 때
      • 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지함

0개의 댓글