[코드잇-자료구조3 : 그래프의 구조와 탐색] 1. 그래프

본 게시물은 코드잇의(codeit) 자료구조 시리즈 강의 세번째 주제인 '그래프의 구조와 탐색'을 듣고 정리한 게시물임을 알려드립니다.

- 강의 url : https://www.codeit.kr/topics/graphs

그래프의 구조와 탐색 - 알고리즘 · 자료구조 강의 | 코드잇

---

1. 연결 관계 데이터와 그래프

자료구조 : 상황에 맞는 방식으로 데이터를 저장하고 사용하기 위함

- 선형적 관계 : 배열, 링크드 리스트

- 계층적 관계 : 트리

- 연결관계 : 그래프

 

그래프

- 연결 데이터를 저장할 수 있는 자료 구조

- 예시 : 다양한 연결 관계

 

2. 그래프 기본

그래프 기본 개념들 (예시 : 친구 관계 데이터 표현)

- (그래프) 노드 : 아래 그림 상의 원형 

- 엣지 : 노드간의 관계

- 인접 : 노드간에 엣지가 있음

   → 지웅-규리 : 서로 인접해있지 않음

- 경로 : 지웅, 규리 사이에 지웅-소원-규리 경로로 연결되어 있고, 그 외 다양한 경로가 있을 수 있음

- 최단 경로 : 다양한 경로들 중 가장 짧은 경로

- cycle : 지웅-현승-소원-지웅 경로

- 차수 : 한 노드가 갖고 있는 엣지의 수

 →  노드에 대해 유용한 데이터를 알아낼 수 있음 (위의 예에서는 차수 = 각 노드의 친구의 수)

  ex. 영훈 노드 = 2, 동욱 노드 = 1

 

3. 방향 그래프

무방향 그래프 (undirected graph)

- 엣지가 방향이 없음

- 방향이 없으므로 아래의 엣지들은 서로 같음

  : (지웅, 현승) = (현승, 지웅)

 

방향 그래프 

ex. 인스타그램 팔로우

- 현승을 떠나서 지웅으로 들어가는 엣지

 → (현승, 지웅) : 떠나는 노드를 항상 앞에 쓴다.

- 맞팔이면 두 방향 다 그려주면 됨

 

방향그래프가 무방향 그래프와 다른 두 가지

1) 경로에도 방향이 있음

2) 노드의 차수

- 출력 차수 : 노드에서 나가는 엣지의 수

- 입력 차수 : 노드로 들어오는 엣지의 수

 

4. 가중치 그래프

예시 : 항공경로 데이터

- 노드 : 공항

- 엣지 : 오가는 비행기 존재 

연결되어있는 것은 같지만, 각 엣지별로 비행시간은 다름 → 이럴 때 엣지에 특정 숫자값을 지정

 

무가중치 그래프 : 모든 엣지에 가중치 같음

무가중치 그래프에 비해 가중치 그래프가 다른점

- 경로의 거리 개념이 바뀜
   : 무가중치 그래프에서 거리는 단순히 경로에 있는 엣지의 수였는데, 가중치 그래프에서 거리는 경로에 있는 모든 엣지 가중치의 합 

5. 그래프 용어/성질 정리

그래프 기본 용어

 

노드: 그래프에서 하나의 데이터 단위를 나타내는 객체. SNS 그래프에서는 하나의 유저가 하나의 노드. 위 그래프에서는 노란색 원이 노드를 나타냄

엣지: 그래프에서 두 노드의 직접적인 연결 관계 데이터. 예를 들어, 페이스북 유저 그래프에서는 두 유저의 친구 관계에 해당하는 데이터. 위 이미지에서는 흰 선들이 그래프의 엣지에 해당.

→ 두 노드 사이에 엣지가 있을 때, “두 노드는 인접해 있다” 라고 표현.

(엣지가 갖는 특성에 따른 그래프의 종류)
- 방향 그래프 (directed graph): 방향 그래프에서는 엣지들이 방향을 갖는다. 인스타그램의 팔로우 관계처럼 한 유저가 다른 유저를 팔로우하는 일방적인 관계를 나타낼 수 있게 해줌
- 가중치 그래프 (weighted graph): 가중치 그래프에서는 엣지들이 연결 관계뿐만 아니라 어떤 정보를 나타내는 수치를 가진다. 그 정보는 예를 들자면 친구 관계에서는 친밀도, 위치 정보 그래프면 두 장소 사이의 거리같은 것

 

차수: 하나의 노드에 연결된 엣지들의 수
- 무방향 그래프 : 하나의 노드에 연결된 엣지들의 수를 나타냄

- 방향 그래프 :노드를 떠나는 엣지의 수를 출력 차수, 노드에 들어오는 엣지의 수를 입력 차수로 구별해서 부른다.
 ex. 위 그래프에서 현승 노드의 차수는 3, 영훈 노드의 차수는 2

 

경로: 한 노드에서 다른 노드까지 가는 길.

 ex. 지웅 노드와 규리 노드는 서로 인접해 있지 않은데, “지웅 - 소원 - 규리” 이 길을 따라가면 지웅 노드에서 규리 노드로 갈 수 있고, 이런 길을 경로라고 한다.

- 경로의 거리

 → 비가중치 그래프: 한 경로에 있는 엣지의 수.
 → 가중치 그래프: 한 경로에 있는 엣지의 가중치의 합.

- 최단 경로: 두 노드 사이의 경로 중 거리가 가장 짧은 경로.
- 사이클: 한 노드에서 시작해서 같은 노드로 돌아오는 경로.

 

연결된 그래프

그래프는 여러 개의 노드와 엣지들을 갖는데, 그렇다고 해서 그래프 안에 있는 모든 노드들이 서로 경로를 통해 연결될 필요는 없음.

SNS 유저 그래프를 만든다고 생각해보자. 세상의 모든 유저들이 서로 어떻게든 꼭 연결되어 있는 것은 아님
그래서 아래 그림처럼 서로 연결된 노드들이, 서로 나눠져 있을 수도 있음. 보기에는 2개의 무리로 나눠져 있지만 어쨌든 하나의 SNS 유저 그래프라고 할 수 있음.

 

조금 더 극단적인 예시를 보면 심지어 이렇게 아예 엣지가 없고 노드만 있는 그래프도 있을 수 있는 것

 

6. [실습] 그래프 노드 구현

7. [실습] 그래프 노드 만들어보기

 

8. 엣지 구현 1 : 인접 행렬

 

그래프의 엣지를 구현하는 방법 중 하나인 '인접 행렬'에 대한 내용

 

인접행렬

- 뜻노드들의 연결 관계(엣지)를 나타내는 2차원 리스트

- 각 노드를 리스트에 저장해 고유 정수 인덱스를 준다.

- 노드 수 X 노드 수 크기의 행렬을 만든다.

- 노들의 엣지 유무 및 가중치에 따라 행렬의 요소를 채운다.

 

 

1) 무방향 그래프

- 인접행렬에서 모든 노드는 스스로와 연결이 안 된 걸로 표시

- 어떤 노드와 어떤 노드가 연결되었는지 확인 가능 (인접행렬의 목표)

※ 왼쪽에 보면 모든 노드에는 인덱스가 있음

 

2) 가중치 그래프

- 행렬 요소에 1대신 가중치를 저장해주면 된다.

 

3) 방향 그래프

- 무방향 그래프와는 다르게 행렬이 대각선을 기준으로 대칭적이지 않음

 

9. [실습] 인접 행렬 구현해보기

 

10. 엣지 구현 2 : 인접 리스트

 

인접 리스트 : 노드들의 인접 데이터를 리스트에 저장하는 방법

- 인접하다 : 두 노드가 연결되어 있다.

- 리스트 : 순서 정보를 저장할 수 있는 자료형

 

- 그래프 노드가 연결된 노드들에 대한 레퍼런스를 저장함

 

예시 : 지하철역 그래프

- 키 : 역이름, 밸류 : 노드 인스턴스

 

그래프 종류에 따른 사용방식 차이

 

1) 무방향 그래프

- A, B가 연결되어 있으면 A의 인접 리스트에 B를 넣고, B의 인접 리스트에도 A를 넣어야 된다.

 

2) 방향 그래프

- A를 떠나서 B로 들어가는 엣지가 있으면 A의 인접 리스트에 B를 넣고, B의 인접 리스트에는 A를 넣지는 않는다. 

- 즉, 엣지가 떠나는 노드의 인접 리스트에만 엣지가 들어가는 노드를 저장시켜 주는 것

 

3) 가중치 그래프

- 튜플을 이용해서 인접한 노드 그리고 그 가중치를 둘 다 저장

 

11. 인접 리스트 연습

 

12. 인접 행렬 vs 인접 리스트

 

13. 그래프 기본 퀴즈