[Data Structure] Graph (그래프)

Graph

📢 Vertex와 Edge로 이루어진 자료구조

---

🎨 Graph 용어

• Vertex(정점) : Graph 상에 위치한 점 (다른 말로 Node라고도 함)
• Edge : Vertex 사이를 잇는 선
• Degree(차수) : Vertex가 가지고 있는 Edge 개수
• Adjacent : 2개의 Vertex u와 v가 Edge를 공유하는 경우

• Incident : 2개의 Edge가 하나의 Vertex를 공유하는 경우

• In-degree : 들어오는 Edge의 개수 / Out-degree : 나가는 Edge의 개수

• Parallel edges (Multiple edges) : 2개의 Vertex가 2개의 Edge로 연결되어 있는 경우

• Self-loop : 자기 자신을 연결하는 Edge가 존재하는 경우

• SubGraph : Graph G의 부분집합으로 이루어진 Graph

• Spanning SubGraph : Graph G의 모든 Vertex를 포함하는 SubGraph

Graph 종류

- Directed Graph (방향 그래프)

모든 Edge가 방향을 가지는 Graph

- Undirected Graph (무방향 그래프)

모든 Eddge가 방향을 가지지 않는 Graph

- Weighted Graph

Edge 각각에 weight (가중치)가 있는 그래프

Graph 경로 표현

• Walk : Graph 내에서 Vertex와 Edge의 연속을 의미 (제약 조건은 없다)

  

• Trail : Edge가 중복되지 않는 Walk

  

• Circuit : Closed Trail

  

• Path : Vertex가 중복되지 않는 Trail

  

• Cycle : 시작와 끝의 Vertex가 같은 Path

  

🔉 그래프 순회 방법

Depth-First Search (DFS)

• 최대한 멀고 깊이 탐색
• Stack을 사용하여 구현할 수 있다.

  

Breadth-First Search (BFS)

• 특정 Vertex에 연결된 모든 Edge를 먼저 탐색
• Queue를 사용하여 구현할 수 있다.

  

---

📋 예제

백준 2178 - 미로 탐색

백준 2178 - 해답

백준 14502 - 연구소

백준 14502 - 해답