그래프

  • 정점(vertex)과 간선(edge)으로 표현한 것
  • 간선의 방향 유무에 따라 단방향 무방향(양방향) 그래프로 나뉨

그래프 표현 방법

1. 인접행렬

  • 모든 정보를 저장.
  • 불필요한 정보 저장이 많고, 그래프 크기가 커지면 메모리 초과가 발생할 수 있음.
  • 갱신이나 삽입, 삭제 등 작업처리 할 때 많이 사용됨. 플로이드 워샬

2. 인접 리스트

  • 필요한 정보만 저장하여 메모리 절약 가능
  • 각 정점에서 이동가능한 정점들을 저장.
  • 특정노드에서부터 탐색일 때 많이 사용 됨.

그래프와 트리의 차이점

그래프 탐색 기법

 

'알고리즘 > 자료구조' 카테고리의 다른 글

Heap  (0) 2020.10.14
Array VS Linked List  (0) 2020.10.14
자료구조  (0) 2020.10.13
  (0) 2020.07.15
스택  (0) 2020.07.15

+ Recent posts