[파이썬] DAY10 그래프

1. 그래프 요소

다대다 관계

대다수의 데이터들은 다대다 관계이다.

 

그래프는 추가적으로 따로 공부하자 중요하다

 

1. 그래프란

정점(V)들의 집합

간선(E)들의 집합

 

2. 무방향 그래프: (Vi, Vj) = (Vj, Vi)

 

파이썬에서는 딕셔너리나 리스트의 특정 형식으로 그래프를 구현한다.

 

 

3. 방향 그래프 : <Vi, Vj> ≠ <Vj, Vi>

Vi 는 머리, 

Vj 는 꼬리를 의미한다.

 

4. 완전 그래프

각 정점에서 다른 모든 정점을 연결하여 가능한 최대의 간선 수를 가진 그래프

최대 간선수

방향 그래프는 무방향 그래프의 2배이다.

  

 

5. 부분 그래프

일부 정점이나 간선 제외하여 만든 그래프

 

6. 가중 그래프, 네트워크

간선마다 가중치(weight)를 할당한 그래프

간선에 정점과 정점이 얼마 만큼 떨어져있는지 표기해준다.

 

---

 

2. 용어 정리

1. 인접: 정점과 정점이 하나의 간선으로 연결되어있다.

간선은 혼자 쓸 수 없으므로 정점에 부속되어 있다.

 

차수: 무방향은 정점(노드)에 연결된 간선 수

방향 그래프에선, 나에서 나가는 건 진출 차수

들어오는 건 진입차수

정점의 차수 = 진출 차수 + 진입 차수

 

2. 경로

경로 길이: 경로를 구성하는 간선의 수

단순 경로: 모두 다른 정점으로 이루어진 경로

사이클 : 시작 정점과 마지막 정점이 같은 경로

 

연결 그래프: 모든 정점들이 간선으로 붙어 있는 그래프

cf) 트리는 사이클이 없는 연결 그래프이다. 즉 1:다 관계인 트리로 바꾸어 더 쉽게 연산할 수 있다.

 

3. 인접행렬

두 정점이 인접하면 1, 인접하지 않으면 0

1) 무방향 그래프: 행의 합 = 열의 합 = 정점의 차수

2) 방향 그래프

   행의 합 = 정점의 진출차수

   열의 합 = 정점의 진입차수

 

* 인접 행렬의 단점

방향 그래프 같은 경우 0이 많고 1이 적은 희소 행렬이 되므로 메모리가 낭비된다.

순차자료구조(인접행렬) -> 연결리스트(인접 리스트)로 보완한다.

 

4. 인접 리스트

 

 

---

3. 그래프의 순회

 

1. 깊이 우선 탐색: 하나부터 먼저 판다.

스택(선입후출)을 반드시 이용한다. 바로 직전 갈림길을 알려준다. 

1) 탐색할 장소, 그래프

2) 정점을 들렸는지 유무 기록하는 장치

3) 스택

끝을 아는 방법: 스택이 모두 비워졌는지 + 모두 들렸는지  확인한다.

 

2. 넓이 우선 탐색: 두루두루 판다.

큐(선입선출)을 반드시 이용한다. 처음 열었던 문을 알려준다. 

1) 탐색할 장소, 그래프

2) 정점을 들렸는지 유무 기록하는 장치

3) 큐

 

 

모든 정점을 다 들렸다. 사이클이 없다.

 

따라서 탐색을 하면 아래 처럼 다대다 에서 1대다인 트리형태로 만들 수 있다.

3. 신장 트리

깊이 우선 신장 트리

넓이 우선 신장 트리

 

그래프는 어떤 데이터가 와도 모두 연산하고 처리할 수 있다.