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

👉  그래프

• 그래프란 사물을 정점(vertex)과 간선(edge)으로 나타내기 위한 도구
• 그래프는 두 가지 방식으로 구현 가능
  • 인접 행렬(adjacency matrix): 2차원 배열을 사용하는 방식
  • 인접 리스트(adjacency list): 연결 리스트를 이용하는 방식

👉  인접 행렬(Adjacency Matrix)

• 인접 행렬에서는 그래프를 2차원 배열로 표현

• 무방향 무가중치 그래프 (자기자신과 간선이 연결되어있지 않을 때 0으로 표기)
  • 모든간선이 방향성을 가지지 않는 그래프를 무방향 그래프라고 한다. 
  • 무방향 비가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접행렬로 출력할 수 있다.
  • 간선의 가중치가 적혀있지 않음

• 방향 가중치 그래프
  • 모든 간선이 방향을 가지는 그래프를 방향 그래프라고 한다.
  • 모든 간선에 가중치가 있는 그래프를 가중치 그래프라고 한다.
  • 방향 가중치 그래프가 주어졌을 때 연결되어있는 상황을 인접행렬로 출력할 수 있다.

👉  인접 리스트(Adjacency List)

• 인접 리스트는 그래프를 리스트로 표현한다.

• 무방향 무가중치 그래프
  • 모든 간선이 방향성을 가지지 않는 그래프를 무방향 그래프라고 한다.
  • 모든 간선에 가중치가 없는 그래프를 무가중치 그래프라고 한다.
  • 무방향 비가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접 리스트로 출력할 수 있다.

• 방향 가중치 그래프
  • 모든 간선이 방향성을 가지는 그래프를 방향 그래프라고 한다.
  • 모든간선에 가중치가 있는 그래프를 가중치 그래프라고 한다.
  • 방향 가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접 리스트로 출력할 수 있다.

👉 그래프의 시간 복잡도

• 인접 행렬: 모든 정점들의 연결 여부를 저장해 O(V²)의 공간을 요구한다.
  • 공간 효율성이 떨어지지만, 두 노드의 연결 여부를 O(1)에 확인할 수 있다.
• 인접 리스트: 연결된 간선의 정보만을 저장하여 O(V + E)의 공간을 요구한다.
  • 공간 효율성이 우수하지만, 두 노드의 연결 여부를 확인하기 위해 O(V)의 시간이 필요하다.

	필요한 메모리	연결 여부 확인
인접 행렬	O(V²)	O(1)
인접 리스트	O(V + E)	O(V)

 

 

👉 최단 경로 알고리즘을 구현할 때, 어떤 자료구조가 유용할까?

• 각각 근처의 노드와 연결되어 있는 경우가 많으므로, 간선 개수가 적어 인접 리스트가 유리

 

 

 

출처: https://fastcampus.co.kr/dev_online_upjscodingtest

JavaScript 코딩테스트 131개 예제 & CS지식으로 끝내기 | 패스트캠퍼스