그래프(Graph)

그래프(graph)

사물을 정점(vertex)과 간선(edge)으로 나타내는 위한 도구

 

- 인접 행렬(adjacency matrix) : 2차원 배열을 사용하는 방식

- 인접 리스트(adjacency list) : 연결 리스트를 이용하는 방식

 

 

인접 행렬(adjacency matrix)

그래프를 2차원 배열로 표현

0	3	7
3	0	무한
7	무한	0

 

 

인접 행렬 - 무방향 무가중치 그래프

모든 간선이 방향성을 가지지 않는 그래프를 무방향 그래프라고 한다.

모든 간선에 가중치가 없는 그래프를 무가중치 그래프라고 한다.

무방향 비가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접 행렬로 출력할 수 있다.

0	1	1	0
1	0	1	0
1	1	0	1
0	0	1	0

 

 

인접 행렬 - 방향 가중치 그래프

모든 간선이 방향을 가지는 그래프를 방향 그래프라고 한다.

모든 간선에 가중치가 있는 그래프를 가중치 그래프라고 한다.

방향 가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접 행렬로 출력할 수 있다.

0	0	7	0
3	0	8	0
0	8	0	0
0	0	4	0

 

 

인접 리스트(adjacency list)

그래프를 리스트로 표현

0 : [(1, 3), (2, 7)]

1: [(0, 3)]

2: [(0, 7)]

 

 

인접리스트 - 무방향 무가중치 그래프

모든 간선이 방향성을 가지지 않는 그래프

모든 간선에 가중치가 없는 그래프

[1, 2],

[0, 2],

[0, 1, 3],

[2]

 

인접 리스트 - 방향 가중치 그래프

모든 간선이 방향을 가지는 그래프를 방향 그래프라고 한다.

모든 간선에 가중치가 있는 그래프를 가중치 그래프라고 한다.

방향 가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접 리스트로 출력할 수 있다.

[ ( 2, 7 ) ],

[ ( 0, 3 ), ( 2, 8 ) ],

[ ( 2,4 ) ],

 

 

그래프의 시간 복잡도

1. 인접 행렬 : 모든 정점 들의 연결 여부를 저장해 O(V²)의 공간을 요구 한다.

공간 효율성이 떨어지지만, 두 노드의 연결 여부를 O(1)에 확인할 수 있다.

 

2. 인접 리스트 : 연결된 간선의 정보만 저장하여 O(V + E)의 공간을 요구한다.

공간 효율성이 우수하지만, 두 노드의 연결 여부를 확인하기 위해 O(V)의 시간이 필요하다.

	필요한 메모리	연결 여부 확인
인접 행렬	O(V²)	O(1)
인접 리스트	O(V + E)	O(V)