99클럽 코테 스터디 30일차 TIL + Graph(2)

학습 키워드

- Graph

 

공부한 내용

그래프 구현 방법

• 그래프는 여러 형태로 구현될 수 있다.
• 주요한 구현 방법에는 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)가 있다.
• 두 가지 구현 방법 중 대부분 인접 리스트 방식을 많이 사용한다.

인접 행렬(Adjacency Matrix)

• 2차원 배열을 사용해 그래프를 표현한다.(2차원 배열에 저장한다.)
• 배열의 요소는 노드 사이의 연결 여부를 나타낸다.
• 아래와 같은 그림에서 연결된 vertex는 숫자 '1'이 데이터로 들어가고 연결되지 않은 vertex는 숫자 '0' 혹은 음수가 들어가게 된다. → 다른 노드와 인접 정점이라면 1, 아니면 0을 넣어준다.
• 그래프에 간선이 많이 존재하는 **밀집 그래프(Dense Graph)**의 경우 사용한다.
• 노드 수보다 간선 수가 많은 dense graph이거나 빠르게 부속(incident)된 간선을 찾을 때 주로 사용한다.
• 즉, 각 정점이 인접하다면 1을 저장하고 그렇지 않다면 0을 저장하는 방식이다.

장점

1. 인접 행렬은 노드의 개수가 적을 때 사용하기 적합하며, 노드 사이의 연결 여부를 상수 시간(O(1))에 확인할 수 있다.
2. 간선의 수에 비례하는 시간 복잡도로 모든 간선을 순회할 수 있다. 따라서 그래프에서 모든 간선을 탐색하는 경우에 유리하다.
3. 구현이 비교적 간단하게 진행된다.

단점

1. 노드 사이의 연결 관계가 적을 때에도 모든 가능한 간선을 표현하기 때문에 공간 복잡도가 높다.
2. 희소 그래프(Sparse Graph)의 경우 인접 행렬은 불필요하게 많은 메모리를 사용하게 된다. 특히 노드의 개수가 많고 간선의 개수가 상대적으로 적은 경우에는 공간 낭비가 심하다.

인접 리스트(Adjacency List)

• 각 노드마다 인접한 노드(정)들을 연결 리스트 형태로 저장한다.
• 그래프 내에 적은 숫자의 간선(Edge)만을 가지는 **희소 그래프(Sparse Graph)**의 경우 사용한다.
• vertex의 갯수만큼 리스트를 사용하고 그래서 자신을 기준으로 연결된 vertex를 리스트에 저장하게 되는 방식이다.
• 각 vertex별로 리스트가 생성이 되고 그 안의 객체로는 자기 자신과 연결된 vertex의 값이 들어가게 된다.

장점

1. 공간 복잡도가 낮다. 인접 리스트는 각 노드마다 인접한 노드들을 연결 리스트 형태로 저장하므로 그래프의 크기에 선형적으로 비례하는 공간만 사용한다. 따라서 희소 그래프에 효율적이다.
2. 각 노드의 인접한 노드들을 순회하는 시간 복잡도는 인접한 간선의 개수에 비례한다. 따라서 인접 리스트는 간선의 수가 적을 때 효율적이다.

단점

1. 노드 사이의 연결 여부를 확인하는 데에는 인접 행렬보다 시간이 더 걸린다. 인접 리스트에서는 특정 노드와 인접한 노드들의 리스트를 탐색해야 하기 때문이다.
2. 모든 간선을 순회하는 데에는 인접 행렬보다 시간이 더 걸린다. 인접 리스트에서는 모든 노드를 순회하고 각 노드의 인접한 노드들을 순회해야 하므로 시간이 더 소요된다. → 간선 정보 확인이 상대적으로 오래걸린다.
3. 구현이 인접행렬에 비해 다소 어렵다.

인접 리스트 vs. 인접 행렬

인접 행렬

• 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph)의 경우

즉, 노드의 개수가 적고 간선의 수가 많을 때 더 낫다.

인접 리스트

• 그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph)의 경우

즉, 노드의 개수가 많고 간선의 수가 적을 때 더 낫다.

• 사실상 그래프 알고리즘 문제에서 가장 중요한 것은 특정 노드에 연결된 모든 노드를 찾는 것이라고 한다.
• 따라서 공간도 적게 사용하면서 위 경우 탐색 시간도 빠른 인접 리스트가 훨씬 많이 사용된다.

 

회고

발생한 문제

- 자료구조에 대한 공부가 부족하다고 생각했다.

 

해결 방법

- 자료구조인 그래프에 대해 공부했다.

 

 

 

참고 자료

- https://cdragon.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Graph%EA%B7%B8%EB%9E%98%ED%94%84#1.%20Graph%20-%20%EA%B7%B8%EB%9E%98%ED%94%84%EB%9E%80%3F-1

- https://hoehen-flug.tistory.com/33