[자료구조] Graph 그래프

Graph 그래프

-정점(vertex/node)들과 정점을 연결하는 간선(edge/arcs)로 이루어진 자료 구조

-G=(V,E)

  === 그래프=(정점의 집합, 간선의 집합)

 

그래프의 종류

-무방향 그래프

-방향 그래프

-가중치 그래프

-완전 그래프

 

그래프 구현 방법

-인접 행렬

  두 정점을 연결하는 간선을 조회할 때 시간복잡도: O(1)

  한 정점의 차수를 구할 때 시간복잡도: O(n)

  모든 간선의 수를 알아낼 때 시간복잡도: O(n²)

  단점: 간선의 수와 관계없이 항상 n² 크기의 2차원 배열을 사용해야 하므로 메모리가 낭비됨.

 

-인접 리스트

 두 정점을 연결하는 간선을 조회하거나 정점의 차수를 알기 위해서는 정점의 인접 리스트를 탐색해야 하므로 정점의 차수만큼의 시간이 필요: O(degree(v))

※degree: 차수

 모든 간선의 수를 알아낼 때 시간복잡도: O(n+e)

 메모리: n+e

 

자료 탐색 방법

- 깊이우선 탐색(DFS: Depth First Search)

: 특정 노드에서 시작하여 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게(끝까지) 탐색하는 방법

 

- 너비우선 탐색(BFS: Breadth First Search)

: 특정 노드에서 시작하여 인접한 노드를 먼저 탐색해나가는 방법

 

 

-잘 정리된 글

https://suyeon96.tistory.com/32

[자료구조] 그래프 (Graph) - 인접행렬 vs 인접리스트, DFS, BFS, Connected Component, Spanning Tree

https://coding-factory.tistory.com/610

[Algorithm] 자료구조 그래프(Graph)란 무엇인가?