[Python] 자료구조 알고리즘, Graph

Graph 

 

그래프는 vertex(정점)과 edge(간선)으로 이루어진 비선형의 자료구조를 말한다.

 

예를 들어 

geometrical (기하학적)으로 표현한 그래프는 이런 모양이고 

 

이 그래프를 Mathmatical (수학적)으로 표현하면 아래와 같다.

V = {0, 1, 2, 3}
E = { (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3) }

 

방향이 있으면 이렇게 된다. ㅎㅎ 우재튜터님의 설명 덕에 그래프들이 귀엽게 보인다. 3번은 인기남❤️ 

 

 

즉, 방향이 있는 그래프와 없는 그래프로 나뉜다. 

• Undirected Graph : 무방향(양방향) 그래프
• Directed Graph : 방향(단방향) 그래프

 

응?

 

 

이렇게 거울 보는 것처럼, 자기가 자기한테 오는 간선을 가진 노드가 있는 그래프도 있다.

수학적으로 표현하면 아래와 같다.

V = {0, 1, 2)
E = { (0, 1), (0, 2), (1, 2), (1, 1) } 

 

 

암튼 그래프의 특징을 좀 더 살펴보면

 

• 사이클 (cycle) 

순환하는 그래프도 있고 아닌 그래프도 있다.

↑ 시작 정점과 종료 정점이 같은 단순 경로 

↑ 계층 구조이면서 순환하지 않는 구조를 가진 그래프, 트리 

 

---

• 인접성 (Adjacency)

그래프에서 두 정점이 간선으로 직접 연결되어 있는지를 뜻하는 말

 

---

• 경로 (Path) 

1 에서 7 까지 가는 경로는 뭐가 있을까?

1 - 0 - 2 - 4 - 6 - 7

1 - 3 - 2 - 6 - 7 

 

등등 다양한 경로가 존재할 수 있다. 즉, length of path가 다를 수 있다!

---

• 연결 (Connected)

 

↑ 얘는 그래프일까 아닐까?

 

 

이것도 하나의 그래프다.

5와 8은 연결되어 있고 1과 5는 연결되어 있지 않을 뿐

---

• 가중치 (Weight)

1 에서 5 까지 가는데 그냥 연결만 하면 될까?

 

최단 경로는 1 - 3 - 2 - 5 지만, 가는 비용을 계산해보면 1 -3 - 6 - 7- 2 - 5가 훨씬 적게 드는 걸 볼 수 있다.

 

즉, 간선에 가중치가 적용된 Weighted Graph가 필요하다.

 

가중치 그래프의 최단 경로를 계산하는 알고리즘은 세가지가 있는데... 우리가.. 구현하게 될 일이.... 암튼 중급 난이도라고 한다. 일단 배웠고 알고있으면 좋으니까..정리함.. 너무 똑똑한 나머지 그냥 한번 풀어보지뭐 해서 풀었는데 너무 쉽게 풀리는 그런 삶을 살고싶다..ㅎ

 

 

다익스트라 알고리즘 (Dijkstra algorithm)

• 가중치 그래프상에 존재하는 특정한 두 정점의 최단거리를 계산하는 알고리즘
• 실제 자동차 네비게이션에 사용되는 알고리즘 중 하나
• 가중치가 음수가 아닌 경우에만 사용 가능

벨만-포드 알고리즘 (Bellman ford algorithm)

• 가중치 그래프에서 단일 출발점에서 다른 모든 정잠까지의 최단 경로를 찾는 알고리즘
• 음수 가중치에도 사용 가능

플로이드-워샬 알고리즘 (Floyd-Warshall Algorithm)

• 가중치 그래프의 모든 쌍에 대해 최단 경로를 찾는 알고리즘
• 음수 가중치에도 사용 가능

---

 

• 신장트리 (Spanning Tree)

모든 정점을 포함하지만 모든 엣지를 포함하고 있지는 않으며 사이클이 없는 연결 그래프.

 

 

 

예를 들어 이런 방향 그래프가 있을떄

 

이런 형태의 다양한 신장 트리가 나올 수 있다.

• 최소 신장 트리 (Minimun Spanning Tree)

신장 트리 중에서도 간선의 가중치 합이 최소가 되는 스패닝 트리

MST는 실제로 네트워크 설계, 도로망 구축 등에서 비용을 최소화하기 위해 굉장히 많이 사용된다.

 

1) 크루스칼 알고리즘: 모든 간선을 가중치 순으로 정렬한 후 스패닝 트리를 구하는 방법

2) 프림 알고리즘: 시작 정점에서 출발해서 최소 가중치의 간선을 선택하며 트리를 확장해 나가는 방법

 

 

어우 눈이 자꾸 감김..

 

---

 

그럼 이제 그래프를 구현하려면 어떻게 해야 할까? 

 

두가지 방법이 있다.

 

1. 인접 행렬

2. 인접 리스트

 

또 이렇게 나타낼 수 있다.

 

{

1 : [ 2, 4, 3] 

2: [ 1, 3]

3: [ 1, 2, 4]

4 : [1, 3]

}

 

 

음 일단 구현 전에 손으로 그릴 수 있어야 한다.