[자료구조] 그래프(Graph)

zzzzsb·2022년 8월 15일
0

그래프 Graph

그래프는 정점(node)과 간선(edge)으로 이루어진 자료구조이다.
조금 더 구체적으로 말하면 각 정점(데이터)들의 관계(연결)를 나타낸 것으로 이해하면 된다.
비선형 자료구조로, 트리도 그래프 중 하나에 속한다.

그래프 용어

  • 정점(node) : vertex 라고도 하며 정점에는 데이터가 저장된다.(0,1,2,3)
  • 간선(edge) : 링크(arcs) 라고도 하며 노드간의 관계를 나타낸다.
  • 인접정점(adjacent node) : 간선에 의해 연결된 정점(위 그림에서 정점 0과 정점 1은 인접 정점)
  • 차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수(정점 0의 차수는 3)
  • 진출 차수(out-degree) : 방향그래프에서 사용되는 용어로 한 노드에서 외부로 향하는 간선의 수
  • 진입 차수(in-degree) : 방향그래프에서 사용되는 용어로 외부 노드에서 들어오는 간선의 수

그래프 종류

그래프는 방향성을 띄고 있는지에 따라 방향 그래프와 무방향 그래프로 나뉜다.
위 그림에서 왼쪽은 방향그래프, 오른쪽은 무방향 그래프이다.

  • 무방향 그래프 : 노드를 연결하는 간선에 방향이 없는 그래프
  • 방향 그래프 : 간선에 방향이 존재하는 그래프로써 해당 방향으로만 이동할 수 있다.
  • 가중치 그래프 : 노드를 이동할 때 지정한 비용이 드는 그래프
  • 완전 그래프 : 모든 노드가 서로 연결되어있는 그래프

그래프 구현 방법

그래프를 구현하는 방법은 크게 두가지가 있다.

  1. 인접 행렬(Adjacency Matrix)
  2. 연결 리스트(Linked List)

1. 인접 행렬(Adjacency Matrix)

그래프의 노드를 2차원 배열로 나타낸 것이다. 해당 노드가 다른 노드에 연결되어있으면 1, 연결되어있지 않으면 0으로 나타낸다.

장점

  • 2차원 배열 안에 모든 노드들의 정보를 담기 때문에 배열의 위치를 확인하면 두 점에 대한 연결 정보를 조회할 수 있다.
  • 즉, 시간 복잡도가 낮다.(O(1))
  • 구현이 상대적으로 간편하다.

단점

  • 모든 노드에 대한 정보를 담아야 하기에 O(N^2)의 시간복잡도가 소요된다.
  • 무조건 2차원 배열이 필요하기에 필요 이상의 공간을 차지한다.

2. 연결 리스트(Linked List)

그래프의 노드들을 리스트로 나타낸 것이다.

장점

  • 노드들의 연결 정보를 탐색할때 O(N)의 시간복잡도
  • 공간을 적게 차지한다.

단점

  • 특정 두 점이 연결되어있는지 확인하기가 까다로움
  • 구현이 상대적으로 복잡하다.

참고 자료

profile
성장하는 developer

0개의 댓글