[알고리즘] 그래프

이번 자료구조인 그래프는 연결관계에 초점이 맞춰져 있다.

그래프는 1. 유방향 그래프 2. 무방향 그래프 가 있다.

유방향 그래프 : 방향이 있는 간선을 갖는다.간선은 단방향 관계를 나타내며 각 간선은 한 방향으로만 진행할 수 있다. 

무방향 그래프 : 방향이 없는 간선을 갖는다.

이런 그래프의 개념을 컴퓨터에 표현하는 방법은 두가지이다.

1, 인접 행렬 : 2차 배열로 그래프의 연결관계를 표현한다

2. 인접 리스트 : 링크드 리스트로 그래프의 연결관계를 표현한다. 

 

두 방식의 차이는?

시간 vs 공간 이다

인접 행렬로 표현하면 즉각적으로 0 과 1 이 연결되었는지 여부로 바로 알 수 있다.

1. 이를 인접 행렬, 2차원 배열로 나타내면 
  0  1  2  3
0 X  O  X  X
1 O  X  O  X
2 X  O  X  O
3 X  X  O  X

그러나, 모든 조합의 연결 여부를 저장해야 되기 때문에 (노드^2) 만큼의 공간을 사용해야 한다.

인접 리스트로 표현하면 즉각적으로 연결되었는지 알 수 없고, 각 리스트를 돌아봐야 한다.

따라서 연결되었는지 여부를 알기 위해서는 최대 간선 만큼의 시간을 사용해야 한다.

대신 모든 조합의 연결 여부를 저장할 필요가 없으니 노드 + 간선 만큼의 공간을 사용한다.

 

즉 시간이 필요하면 인접 행렬, 공간이 필요하면 인접 리스트를 하면 된다.