그래프 이론 기초 (Graph, Vertex, Edge, Indegree, Outdegree, Weight)

https://blog.naver.com/jhc9639/222289089015

[알고리즘 강의] 2주차. 그래프이론, 인접행렬, 인접리스트, DFS, BFS, 트리순회

---

그래프(Graph)

정점(vertex)와 간선(edge)의 집합

---

정점(Vertex)와 간선(Edge)

• 정점(vertex)
  • 노드(node)라고도 불리며 그래프를 형성하는 기본 단위
  • 분할할 수 없는 객체이자 점으로 표현되는 위치, 사람, 물건 등
  • 보통 u와 v 로 많이 나타내는데, u는 from v는 to
• 간선(edge)
  • 정점을 잇는 선으로 관계, 경로 등
  • 단방향,양방향 간선

버텍스와 엣지의 예시 (출발지, 목적지, 경로 / 사람과 사람 간의 마음 등)

---

Indegree와 Outdegree

 

u: 출발점(from) - 온양관광호텔

v: 도착점(to) - 남성역

 

온양관광호텔에서 남성역에 가는 경로는 총 6개 outdegree

남성역에서 온양관광호텔로 돌아오는 경로는 총 7개 indegree

---

가중치(weight)

 

정점과 정점사이에 드는 비용.

2시간 14분 소요. 3450원 듦 / 1시간 36분, 여러가지 비용