방향 그래프(Directed Graph)

방향 그래프(Directed Graph, Digraph) 는 각 간선(Edge)에 방향성이 부여된 그래프이다.
즉, 간선이 단방향이므로 A → B 는 이동할 수 있지만 B → A 로는 이동할 수 없다.

방향 그래프는 일방향 관계가 있는 다양한 시스템을 모델링할 수 있다.
웹, 사회 연결망, 컴퓨터 시스템, 생물학적 네트워크 등 다양한 분야에서 방향 그래프를 활용한 알고리즘과 모델이 개발되고 있다.

방향 그래프 특징

간선이 한 방향(→)으로만 연결됨
단방향 관계를 표현할 때 사용 (예: 팔로우 관계, 웹 페이지 링크)
진입 차수(In-degree)와 진출 차수(Out-degree) 개념이 존재
- 진입 차수(In-degree): 해당 정점으로 들어오는 간선의 개수
- 진출 차수(Out-degree): 해당 정점에서 나가는 간선의 개수

방향 그래프의 표현 방법

방향 그래프 예시

1
2
3
  A → B
  ↓   
  C → D

A → B (A에서 B로 이동 가능)
A → C (A에서 C로 이동 가능)
C → D (C에서 D로 이동 가능)
B에서 A로 이동할 수 없음! (단방향 구조)

방향 그래프의 인접 행렬(Adjacency Matrix) 표현

	B	C	D
A	1	1	0
B	0	0	0
C	0	0	1
D	0	0	0

설명

A → B, A → C, C → D가 존재하므로 1로 표시됨
B에서 다른 노드로 가는 간선이 없으므로 행(B)이 모두 0

방향 그래프의 인접 리스트(Adjacency List) 표현

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
graph = {
    'A': ['B', 'C'],
    'B': [],
    'C': ['D'],
    'D': []
}

# 그래프 출력
for node in graph:
    print(node, ":", graph[node])

출력 결과

1
2
3
4
A : ['B', 'C']
B : []
C : ['D']
D : []

방향 그래프의 특성

진입 차수(In-degree)와 진출 차수(Out-degree)
각 노드의 간선 개수를 보면:
- A의 진출 차수: 2 (B, C로 이동 가능)
- B의 진입 차수: 1 (A에서 들어옴)
- C의 진출 차수: 1 (D로 이동 가능)
- D의 진입 차수: 1 (C에서 들어옴)
방향 그래프의 경로(Path)
- 경로(Path): 특정 노드에서 다른 노드까지 이동하는 순서
  - A → C → D (가능)
  - D → A (불가능)
사이클(Cycle)
- 방향 그래프에서 A → B → C → A 처럼 한 바퀴 돌면 다시 출발점으로 돌아오는 경우 사이클이 존재한다고 한다.
- 방향 그래프에서 사이클이 없는 경우 “DAG(Directed Acyclic Graph)“라고 한다.

방향 그래프의 구현

방향 그래프 생성 (Python)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class DirectedGraph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, u, v):
        if u not in self.graph:
            self.graph[u] = []
        self.graph[u].append(v)

    def display(self):
        for node in self.graph:
            print(node, ":", self.graph[node])

# 그래프 생성
g = DirectedGraph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('C', 'D')

# 그래프 출력
g.display()

출력 결과

1
2
A : ['B', 'C']
C : ['D']

방향 그래프의 종류

단순 방향 그래프(Simple Directed Graph)
- 자기 루프(self-loop)가 없고 정점 쌍 사이에 최대 하나의 간선만 존재
다중 방향 그래프(Multigraph)
- 두 정점 사이에 여러 개의 간선이 허용되는 그래프
완전 방향 그래프(Complete Directed Graph)
- 모든 정점 쌍 사이에 양방향으로 간선이 존재하는 그래프
- n개의 정점을 가진 완전 방향 그래프는 n(n-1)개의 간선을 가짐
가중치 방향 그래프(Weighted Directed Graph)
- 각 간선에 가중치(비용, 거리, 시간 등)가 할당된 그래프
비순환 방향 그래프(Directed Acyclic Graph, DAG)
- 사이클이 없는 방향 그래프
- 작업 스케줄링, 의존성 관리 등에 널리 사용됨

방향 그래프의 탐색 알고리즘

깊이 우선 탐색 (DFS, Depth-First Search)

한 방향으로 끝까지 탐색 후 백트래킹
스택(Stack) 또는 재귀(Recursion) 사용

1
2
3
4
5
6
7
8
9
def dfs(graph, node, visited):
    if node not in visited:
        visited.add(node)
        print(node, end=" ")
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited)

graph = {'A': ['B', 'C'], 'B': [], 'C': ['D'], 'D': []}
dfs(graph, 'A', set())  # A C D B

너비 우선 탐색 (BFS, Breadth-First Search)

가까운 노드부터 탐색 (큐 사용)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
from collections import deque

def bfs(graph, start):
    queue = deque([start])
    visited = set()

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            print(node, end=" ")
            queue.extend(graph[node])

graph = {'A': ['B', 'C'], 'B': [], 'C': ['D'], 'D': []}
bfs(graph, 'A')  # A B C D

방향 그래프의 활용

소셜 네트워크 분석 (Twitter, Instagram)
- 트위터에서는 A가 B를 팔로우하면 A → B로 방향 간선을 가짐
웹 페이지 랭킹 (Google PageRank)
- 웹 페이지 간 링크를 방향 그래프로 나타냄
네트워크 라우팅 (인터넷 패킷 경로 탐색)
- 패킷이 흐르는 방향을 그래프로 표현
작업 스케줄링 (Topological Sorting)
- 작업 간의 의존 관계를 DAG(Directed Acyclic Graph)로 표현하여 실행 순서를 정함
인공지능 & 머신러닝
- 신경망(Neural Network)의 구조가 방향 그래프로 표현됨

방향 그래프(Directed Graph)#

방향 그래프 특징#

방향 그래프의 표현 방법#

방향 그래프의 인접 행렬(Adjacency Matrix) 표현#

방향 그래프의 인접 리스트(Adjacency List) 표현#

방향 그래프의 특성#

방향 그래프의 구현#

방향 그래프의 종류#

방향 그래프의 탐색 알고리즘#

방향 그래프의 활용#

참고 및 출처#