그래프 이론

그래프의 종류

• Directed Graph (방향 그래프) : 간선간에 방향이 존재한다.
• Undirected Graph (무방향 그래프) : 간선간에 방향이 존재하지 않는다.
• Weighted Graph (가중 그래프) : 간선에 weight가 존재한다.

 

그래프에서 좀더 깊게 들어가면

• Subgraph(부분 그래프) : V' ⊆ V, E' ⊆ E, 그래프에 포함된 그래프
• Complete graph(완전 그래프) : 모든 노드 간에 간선이 연결된 그래프
• Path : 한 노드에서 특정 노드 까지 도착한 노드들의 모임 (simple path는 중복된 노드 도달 불가)
• reachable(도달 가능) : 임의의 노드에서 다른 노드 까지 도달이 가능하다.
• Connected : 모든 vertex가 연결되어 있는 Undirected Graph
• Strongly Connected : Directed Graph에서 모든 vertex가 연결되어 있다.
• Cycle : 출발한 노드로 다시 돌아 올 수 있는 그래프 vs Acycle : 출발한 노드로 다시 돌아오지 못한다.

 

그래프를 구현하는 방법

• 에지 리스트
• 인접 행렬
• 인접 리스트

 

에지 리스트

에지 리스트는 edge를 중심으로 그래프를 표현한다. 출발 노드와 도착 노드를 지정하여 에지를 포현한다.

에지 리스트는 표에서도 볼 수 있듯이 특정 노드와 관련되어 에지를 탐색하기는 쉽지 않다. 그래서 에지 중심의 알고리즘인 벨만 포드나 크루스칼 알고리즘에 사용된다.

• 크루스칼 알고리즘 : 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용하는 알고리즘이다. (최소 신장 트리)
• 벨만 포드 알고리즘 : 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘이다. edge의 가중치가 음수일 때도 최단 거리를 구할 수 있다.

디익스트라 알고리즘 

• 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하여 한단계씩 최단 거리를 구해나간다.
• 음수 간선이 없을 때 최적의 해를 구할 수 있다.
• 시간 복잡도는 O(ElongV) 

벨만 포드 알고리즘

• 매 단계마다 모든 간선을 전부 확인하면서 모든 노드간의 최단 거리를 구한다. (디익스트라 알고리즘에서의 최적해를 항상 포함하게 된다.)
• 음수 간선이 있어도 최적의 해를 찾을 수 있다. 
• 시간 복잡도는 O(VE)

 

인접 행렬

2차원 배열을 자료구조로 이용하여 그래프를 표현한다. 노드 중심으로 그래프를 표현한다. 

장점

• 두 노드를 연결하는 에지의 여부와 가중치 값은 배열에 직접 접근하면 바로 확인 할 수 있다. 

단점

• 노드와 관련된 edge를 탐색하려면 N번 접근해야 한다. 
• 노드 개수에 비해 edge가 적을 때는 공간 효율성이 떨어진다.
• 노드 개수가 많은 경우는 2차원 배열 선언 자체를 할 수 없을 수도 있다.

 

인접 리스트

ArrayList로 그래프를 표현한다. 

장점

• 노드와 연결되어 있는 에지를 탐색하는 시간이 매우 뛰어나다. 
• 노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러가 발생하지 않는다.

 

	인접 행렬	인접 리스트
간선 정보를 저장하는 메모리 공간	O(V^2)	O(E)
특정 2개의 노드가 인접 했는지 (adjacent)	O(1)	V의 노드 에서 간선의 수 = deg(a) W의 노드에서 간선의 수 = deg(b) O(min(deg(V), deg(W)))  -> 무방향 O(deg(V)) -> 방향 그래프
edge와 노드가 연결되어 있는지 검사 (incident)	O(V) 노드의 수만큼 탐색	O(deg(V))

 

그래프를 활용한 알고리즘

1. BFS, DFS (그래프 traverling)

 

2. 서로소 집합(유니온 파인드)

서로소 집합  보러가기

 

3. 최소 신장 트리 구하기

• 프림의 알고리즘 (그리디 알고리즘으로 최소 신장 트리 구하기)  O(ElogV)
• 크루스칼의 알고리즘 (유니온 파인드를 사용해 최소 신장 트리 구하기) O(ElogV)  간단하게 설명하자면 가중치를 기준으로 edge를 오름차순으로 정렬 한 뒤 작은 수 부 터 탐색하면서 cycle만 없게 탐색하는 것이다. cycle이 있는지 없는지 검사할 때, 유니온 파인드가 사용된다.

 

4. 최단 거리 구하기

• 디익스트라 알고리즘 
• 벨만 포드 알고리즘
• 플로이드 워셜 알고리즘 (모든 노드간의 최단 거리 구하기)

 

5. 위상 정렬

사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. 시간 복잡도는 O(V+E)

위상정렬 보러가기

 

6. 강한 연결 요소 추출 알고리즘

• 코사리주 알고리즘 (DFS를 2번 하여 강한 결합 요소를 찾는다)
• 타잔 알고리즘 (DFS를 한번만 수행해 강한 결합 요소를 찾는다) 코딩 테스트에서 이 알고리즘이 더 많이 쓰인다.

강한 결합 요소 보러가기