[알고리즘] 그래프 알고리즘

·2022년 5월 9일
0

그래프

정점(노드)간선(엣지)으로 이루어진 자료구조를 의미한다. 간선은 방향을 가질 수 있으며 방향과 순환의 유무에 따라 종류가 나뉘게 된다.

그래프의 표현

출처 : https://howtolivelikehuman.tistory.com/75

인접 행렬 그래프

가중치가 없는 경우

출처 : https://sarah950716.tistory.com/12

가중치가 있는 경우

출처 : https://yoongrammer.tistory.com/84

특징

  • 이차원 배열을 주로 사용한다.
  • 이동할 수 있으면 1, 없으면 0 으로 표기한다.
  • 가중치가 있다면 가중치를 값으로 표기한다.
  • 가중치가 0인경우 대비하기 위해 ∞로 표기하기도 한다.
  • 무방향 그래프의 경우 대각 성분을 기준으로 대칭성을 가진다.

장점

  • 직관적이며 쉽게 구현 가능하다.
  • O(1)의 시간복잡도를 가진다

단점

  • 불필요한 정보의 저장이 많다.
  • 특정 노드와 연결된 노드들이 몇 번 노드인지 확인하기 위해 모든 노드의 연결 관계를 확인해야 한다. 이 경우 시간복잡도가 O(V)가 된다.(V는 노드의 개수)
  • 그래프가 커지면 메모리 초과가 발생할 수 있다.

인접 리스트

가중치가 없는 경우

출처 : https://sarah950716.tistory.com/12

가중치가 있는 경우

출처 : https://yoongrammer.tistory.com/84

특징

  • 링크드 리스트를 이용해 구현한다.
  • 가중치가 있는 경우 추가로 공간을 만들어 저장한다.

장점

  • 실제로 연결된 노드들에 대한 정보만 저장한다.
  • 간선의 개수에 비례하는 메모리만 차지한다.
  • 특정 노드와 연결된 노드들을 확인하기 위해 실제로 연결된 노드들만 탐색 할 수 있다.
  • 이 경우 시간복잡도는 O(E)이다. (E는 간선 개수)

단점

  • 행렬[i][j] 이렇게 배열처럼 탐색 할 수 없고 리스트를 하나하나 돌면서 노드 i노드 j가 연결되어 있는지 찾아야 한다.
  • 이 경우 시간복잡도는 O(V)이다.

참고자료

0개의 댓글

관련 채용 정보