[자료구조] 그래프

이창민·2022년 8월 29일
0

자료구조

목록 보기
4/5

Graph

  • 정점과 간선의 집합이다.(트리는 싸이클이 없는 그래프)
    - 연결되어 있는 객체간의 관계를 표현할 수 있음

종류

무방향 그래프(Undirected Graph)

  • 말 그대로 정점과 간선의 연결관계에서 방향성이 없는 그래프
  • Degree : 각 정점에 연결된 Edge의 개수

방향 그래프(Directed Graph)

  • 정점과 간선의 연결관계에서 방향성이 있는 그래프
  • Degree
    - 각 정점에서 나가는 간선의 개수 OutDegree
    • 각 정점으로 들어오는 간선의 개수 InDegree

가중치 그래프(Weighted Graph)

  • 간선에 가중치(비용)이 할당된 그래프

구현 방법

인접 행렬(Adjacent matrix)

  • 정방 행렬을 사용하는 방법
  • NxN Boolean 행렬 matirx[i][j] == 1 이면 i -> j 간선이 존재한다는 뜻
  • 해당하는 위치의 value 값을 통해 정점간 연결 관계를 O(1)로 파악 가능
  • 간선의 개수와 상관없이 V^2의 공간 복잡도를 가짐
  • Dense Graph(간선이 정점보다 많음) 표현에 적당

인접 리스트(Adjacent List)

  • 연결 리스트를 사용하는 방법
  • 정점의 인접 리스트를 확인해야해 정점이 연결되었는지 확인하는 데 오래 걸림
  • 공간 복잡도는 O(E + V)
  • Sparse Graph(정점이 간선보다 많음) 표현에 적당
  • 무방향 그래프에서 간선은 2번 저장됨

Graph 탐색

깊이 우선 탐색(DFS)

  • 임의의 정점에서 연결되어 있는 한 정점으로만 나아가는 방법으로 탐색
  • 자료구조로 Stack 을 사용해 탐색할 정점의 순서 기록
  • 연결된 정점이 있을 때까지 계속 연결하다가 더이상 연결되지 않은 정점이 없으면 바로 그 전단계의 정점에서 연결할 수 있는 정점이 있는지 살펴봄
  • 시간 복잡도 : O(V+E)

너비 우선 탐색(BFS)

  • 임의의 정점에서 연결되어 있는 모든 정점으로 나아가는 방법으로 탐색
  • 자료구조로 Queue 를 사용해 탐색할 정점의 순서를 기록
  • Queue를 dequeue 해 해당 정점과 연결된 정점들을 enqueue
  • 시간 복잡도 : O(V + E)
  • BFS로 구한 경로는 최단 경로

신장 트리(Spanning Tree)

  • 그래프 내 모든 정점이 연결되어 있으면서 사이클이 없는 트리
  • 하나의 연결 그래프가 있으면 신장트리는 여러개가 존재할 수 있음

최소 신장 트리(MST)

  • 그래프의 신장트리 중 간선 비용의 합이 최소인 신장트리
  • MST를 찾는 대표적인 알고리즘 크루스칼, 프림

크루스칼 알고리즘(Kruskal Algorithm)

  • 그리디 알고리즘
  • 그래프의 간선들을 가중치의 오름차순으로 정렬한 후, 사이클을 형성하지 않는 선에서 정렬된 순서대로 간선 선택
  • 사이클의 형성 유무는 Union&Find 자료구조 사용
  • 시간 복잡도 : O(E log E)

프림 알고리즘(Prim Algorithm)

  • 그리디 알고리즘
  • 임의의 정점에서 시작
  • 정점에서 인접하는 정점들 중 최소 비용의 간선이 존재하는 정점을 선택, 반복
  • 시간 복잡도 : O(E log V)

참고자료

https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html
https://chanhuiseok.github.io/posts/algo-33/
https://goodgid.github.io/Prim-Algorithm/

profile
android 를 공부해보아요

0개의 댓글