[자료구조] 그래프

💡 그래프

: 그래프는 연결되어 있는 정점와 정점간의 관계를 표현할 수 있는 자료구조이다.

: 비선형구조로써, 연결 관계 표현에 초점이 맞춰져 있다.

 

[ 선형구조 vs 비선형 구조 ]

선형 구조란 자료를 구성하고 있는 데이터들이 순차적으로 나열되어있는 형태이다.

비선형 구조란 데이터가 계층적 혹은 망으로 구성되어있는 형태이다.

선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있다.

비선형구조에는 그래프, 트리가 있고 선형구조에는 스택, 큐가 있다.

 

 

💡 그래프의 용어

- 노드(Node)

  : 연결 관계를 가진 각 데이터를 의미한다. 정점(Vertex)이라고도 한다.

- 간선(Edge)

  : 노드 간의 관계를 표시한 선.

- 인접 노드(Adjacent Node)

  : 간선으로 직접 연결된 노드(또는 정점)

 

💡 그래프 종류

- 유방향 그래프(Directed Graph)

   : 방향이 있는 간선을 갖는다.

   : 간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행할 수 있다.

- 무방향 그래프(Undirected Graph)

   : 방향이 없는 간선을 갖는다.

 

 

💡 그래프 표현방법

1) 인접 행렬(Adjacency Matrix)

: 2차원 배열로 그래프의 연결 관계를 표현

2) 인접 리스트(Adjacnecy List)

: 링크드 리스트로 그래프의 연결 관계를 표현

[ 예시 ]

    2 - 3

    ⎜

0 - 1

 

1) 인접 행렬로 표현

	0	1	2	3
0	X	O	X	X
1	O	X	O	X
2	X	O	X	O
3	X	X	O	X

graph = [ [False, True, False, False], [True, False, True, False], [False, True, False, True], [False, False, True, False] ]

 

2) 인접 리스트로 표현

0 -> 1
1 -> 0 -> 2
2 -> 1 -> 3
3 -> 2

graph = { 0: [1], 1: [0, 2], 2: [1, 3], 3: [2] }

 

 

💡 인접 행렬 vs 인접 리스트

= 시간 VS 공간

  인접 행렬으로 표현하면 즉각적으로 0과 1이 연결되었는지 여부를 바로 알 수 있다. 그러나, 모든 조합의 연결 여부를 저장해야 되기 때문에 O(노드^2) 만큼의 공간을 사용해야 한다.

  인접 리스트로 표현하면 즉각적으로 연결되었는지 알 수 없고, 각 리스트를 돌아봐야 한다. 따라서 연결되었는지 여부를 알기 위해서 최대 O(간선) 만큼의 시간을 사용해야 한다. 대신 모든 조합의 연결 여부를 저장할 필요가 없으니 O(노드 + 간선) 만큼의 공간을 사용하면 됩니다.