자료구조_그래프 +)신장트리, 최소신장트리

그래프

 

1. 그래프의 약자

Graph(그래프)
Graph : G = (V, E) 이 두개가 세트임
V: vertex (트리에선 노드)
E: a set of pairs of nodes (엣지)
▼▼▼▼▼▼▼▼▼▼
V = {0,1,2,3}
E = {(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)}
u: tail of the edge
v: head of the edge
<u, v> =/= <v, u>

 

2. 방향/무방향 그래프

양방향(무방향) 그래프: <u, v> == <v, u>
단방향(방향) 그래프: <u, v> =/= <v, u>

 

그래프에서 (1,1)이 있다면, 자신이 자신에게로 향한 것임(그런 그래프도 있을 수 있음)

 

3. 그래프의 용어 (중요도 🌟 🌟)

🔸사이클(cycle): 시작 정점과 종료 정점이 같은 단순 경로 (그런 그래프를 사이클이 있는 그래프라고 부름)

🔸인접성(adjacency): 그래프에서 두개의 정점이 간선으로 직접 연결되어 있다면 인접하다고 말함. (그냥 서로 선이 연결돼있으면 인접한거)

🔸경로(path): 시작 정점에서 종료 정점까지 가는 다양한 경로
이때 다양한 경로가 존재할 수 있다 == length of path 가 다를 수 있음 (짧은 경로가 있을 수 있고, 긴 경로가 있을 수 있음)

🔸연결(Connected): 어떤 노드로 다른 노드로 갈 수 있느냐를 봤을 때, 갈 수 있다면 연결되어있다고 말함
(즉 연결되어있지 않는 그래프가 있을 수 있음. 중간에 경로가 끊긴 겨)

 

🔸가중치(weight): 지도로 따지자면 하나의 경로에 걸리는 시간이 가중치라고 생각하면 됨. 경로에 부하된 가중치가 있음.

그 가중치로 최단의 경로를 제시해줌. 거리가 짧다고 가중치가 낮다고 볼 수 없음.

 

---

4. 트리는 그래프 중 하나

: 트리도 그래프 중 하나이고, 특정한 조건을 만족하여 트리라고 부르는 것

그 조건은,
두 개의 노드 사이에 반드시 1개의 경로만 가지면서, 사이클이 존재하지 않는 방향 그래프
(방향이 위에서 아래로 떨어지는 상하 그래프)

 

5. 신장트리(Spanning Tree)

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

(즉 그래프가 모두 간선으로 이어져있지는 않음)

 

6. 최소신장트리(Minimum Spanning Tree, MST)

: 신장 트리 중에서도 간선의 가중치 합이 최소가 되는 신장트리를 말함.
MST는 실제로 네트워크 설계, 도로망 구축 등에서 비용을 최소화하기 위해 굉장히 많이 사용

최소신장트리의 알고리즘(일단 지금은 중요하지 않으니 용어만 알아두기)
크루스칼 알고리즘: 모든 간선을 가중치 순으로 정렬한 후 스패닝 트리를 구하는 방법
프림 알고리즘: 시작 정점에서 출발해서 최소 가중치의 간선을 선택하며 트리를 확장해 나가는 방법

 

7. 그래프를 구현하는 2가지 방법 (중요도 🌟 🌟 🌟 )

- 인접 행렬: 

방향그래프인지, 무방향 그래프에 따라 인접행렬이 달라짐. 무방향 그래프일 경우 인접 행렬은 대칭을 이루게 됨

장점: 행렬이기 때문에 사용하기 편할 수 있음. 근데 행이나 열이 너무 많아지면 표를 나타내는 공간을 많이 차지하기 때문에 쓰기가 어려움 (공간복잡도)

- 인접 리스트: 

연결리스트처럼 표현함

장점: 공간을 덜 차지함 (vertex가 많을 때 인접리슽를 사용하면 좋음)

 

---

📁 추가 내용

우리의 관심사는 '순회'임
즉, 주어진 그래프의 특정 정점에서 도달 가능한 모든 정점을 찾는 것
DFS, BFS

 

DFS(깊이우선탐색) 코드 구현하는 방법 (요약)

탐색할 때 마킹을 해야 함. (해당 vertex는 방문했다는 표시, 즉 표시할 리스트가 필요함)
나랑 인접한 vertex 중에 하나 선택해서 방문함. 그리고 방문하지 않은 vertex로 감
스택에 쌓는다
만약 이미 방문했을 경우 pop한다.(back 한다)
모두 방문했을 경우, 스택에 쌓인 걸 순서대로 pop한다