[자료구조] 진입차수란?

진입차수(Indegree)란?

그래프 이론(Graph Theory)은 네트워크 구조를 모델링하고 분석하는 데 사용되는 수학적 도구입니다.

 

그 중에서도 "진입차수(Indegree)"는 방향 그래프(Directed Graph)에서 매우 중요한 개념 중 하나입니다.

 

이 개념은 어떤 정점으로 들어오는 간선의 수를 나타내며, 그래프 내의 연결 관계를 이해하는 데 도움이 됩니다.

 

그래프에 대한 개념을 다시 잡고 싶으시면 아래의 링크로 이동하시면됩니다.

 

https://sonlife97.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%9E%98%ED%94%84%EB%9E%80

[자료구조] 그래프란?

 

진입차수란 무엇인가요?

 

진입차수(Indegree)는 특정 정점(vertex)에 연결된 간선의 개수를 의미합니다. 이 개념은 주로 방향 그래프에서 사용됩니다.

 

방향 그래프는 정점 간의 방향성이 있는 간선으로 이루어져 있으며, 진입차수는 특정 정점으로 들어오는 간선의 수를 나타냅니다.

간단한 예시로 이해해보겠습니다. 아래 그래프를 살펴봅시다.

A --> B
|     |
v     v
C --> D

이 그래프에서 각 정점의 진입차수는 다음과 같습니다

- 진입차수(Indegree) of A: 0 (다른 정점에서 들어오는 간선이 없음)
- 진입차수(Indegree) of B: 1 (A에서 B로 들어오는 간선이 1개)
- 진입차수(Indegree) of C: 1 (A에서 C로 들어오는 간선이 1개)
- 진입차수(Indegree) of D: 2 (B와 C에서 D로 들어오는 간선이 각각 1개씩, 총 2개)

 

진입차수의 활용

 

진입차수는 그래프 이론과 관련된 다양한 문제 및 알고리즘에서 활용됩니다. 예를 들어, 다음과 같은 상황에서 유용하게 사용됩니다.

1. 위상 정렬(Topological Sorting)

진입차수 정보를 이용하여 방향 그래프의 위상 정렬을 수행할 수 있습니다. 위상 정렬은 그래프의 정점들을 선형 순서로 나열하는 작업으로, 작업의 종속성이 있는 일정을 계획하거나 작업 흐름을 분석하는 데 사용됩니다.

2. 그래프 순회

그래프 내의 정점들을 순회하거나 검색할 때, 진입차수 정보를 이용하여 시작점을 선택할 수 있습니다. 진입차수가 0인 정점은 그래프 내에서 시작점이 될 수 있습니다.

진입차수는 그래프 이론에서 매우 유용한 개념 중 하나이며, 방향 그래프의 구조를 이해하고 분석하는 데 필수적입니다. 따라서 그래프 이론을 다룰 때 진입차수 개념을 잘 이해하는 것이 중요합니다.