[자료구조] 그래프 (Graph)

래프는 정점(Vertex)과 엣지(Edge)로 이루어진 자료구조로, 관계를 표현하는 데 사용된다.

그래프의 정의:

 

• V: 정점(Vertex)들의 집합
• E: 정점을 연결하는 엣지(Edge)들의 집합

 

 

아래와 같은 그래프 형태

 

경로(Path)

• 그래프에서 한 정점에서 다른 정점으로 이동하는 과정을 경로라고 한다.
• 유효한 경로: 한 번 지난 엣지를 다시 사용하지 않고 연결되는 정점의 나열
• 예제:
  • ✅ 올바른 경로: 3 -> 2 -> 1 -> 5
  • ❌ 잘못된 경로: 3 -> 2 -> 1 -> 2 -> 5 (같은 엣지를 중복 사용)

 

사이클(Cycle)

• 시작 정점과 끝 정점이 같은 경로를 사이클(Cycle) 이라고 한다.
• 예제: 3 -> 2 -> 5 -> 4 -> 3

 

그래프의 종류

1️⃣ 무방향 그래프 (Undirected Graph)

• 엣지에 방향이 없음
• 두 정점 간 이동이 양방향 가능
• 예제: (A,B)=(B,A)

2️⃣ 유방향 그래프 (Directed Graph, DAG 포함)

• 엣지에 방향이 있음
• 특정 방향으로만 이동 가능
• 예제: A->B 와 B->A 는 다름

 

그래프 표현 방법

1️⃣ 인접 행렬 (Adjacency Matrix)

• 정점 n개인 그래프를 n × n행렬로 표현
• 행렬의 원소 값이 1이면 엣지가 존재, 0이면 엣지가 없음

✅ 특징

• 메모리 사용량: O(n^2)
• 특정 엣지 (u,v) 존재 여부 확인: O(1)
• 정점 u의 모든 인접 노드 탐색: O(n)
• 새로운 엣지 삽입: O(1)

✅ 예제

  1  2  3  4  5
1 0  1  0  0  0
2 1  0  1  0  1
3 0  1  0  1  0
4 0  0  1  0  1
5 0  1  0  1  0

G[2][3]=1 이므로 2→3 엣지 존재

 

 

2️⃣ 인접 리스트 (Adjacency List)

• 각 정점에 연결된 정점들을 리스트로 저장
• 연결 리스트를 사용해 구현

✅ 특징

• 메모리 사용량: O(n+m)
• 특정 엣지 (u,v) 존재 여부 확인: O(deg(u))
• 정점 u의 모든 인접 노드 탐색: O(deg(u))
• 새로운 엣지 삽입: O(1)

O(deg(u)) = 정점 u의 인접한 노드 개수만큼 실행되는 연산

 

✅ 예제

1: [2]
2: [1, 3, 5]
3: [2, 4]
4: [3, 5]
5: [2, 4]

 

 

 

 

그래프 탐색 (Graph Traversal)

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

• 한 방향으로 최대한 깊이 탐색 후 돌아옴
• 스택(Stack) 또는 재귀(Recursion) 사용

✅ 시간 복잡도: O(n+m)

✅ 예제 (재귀)

def dfs(graph, node, visited):
    visited[node] = True
    print(node, end=" ")
    for neighbor in graph[node]:
        if not visited[neighbor]:
            dfs(graph, neighbor, visited)

 

 

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

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

✅ 시간 복잡도: O(n+m) (m = 엣지 개수)

✅ 예제 (큐 사용)

from collections import deque

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