자료구조 2

그래프

---

그래프란?

연결되어 있는 객체 간의 관계를 표현하는 자료구조

그래프의 정의

정점, 간선으로 이루어진 자료구조 Graph G = (V, E)

• V : 정점(Vertex)의 집합(유한 집합)
• E : 간선(Edge)의 집합(정점 쌍으로 표현)

그래프의 종류

1. 무방향성 그래프(Undirected Graph)
   • 정점 사이의 연결 관계가 방향성이 없는 그래프
2. 방향성 그래프(Directed Graph)
   • 정점 사이의 연결 관계가 방향성이 있는 그래프
3. 가중치 그래프(Weighted Graph) & 네트워크(Network)
   • 간선에 가중치(비용 등)가 할당된 그래프
   • 예) vertex : 도시, edge : 도로, 가중치 : 거리

그래프 표현 예시

//무방향성 에지는 ()로 표현
V(G1) = {0, 1, 2, 3}, E(G1) = {(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)}
V(G2) = {0, 1, 2, 3}, E(G2) = {(0, 1), (0, 2)}
//방향성 에지는 <>로 표현
V(G3) = {0, 1, 2}, E(G3) = {<0, 1>, <1, 0>, <1, 2>} 

예시

• 도로망
• 네트워크
• 지하철 노선도

$$