[알고리즘 정리] 그래프 (Graph)와 Floyd warshall 알고리즘

그래프란?

정점과 간선으로 이루어진 자료구조를 말한다. 무슨 소리지? 싶어 그림을 첨부했다.

대충 이렇게 생겼으면 그래프라고 할 수 있다.

 

정점(Vertex)은 노드(Node)라고도 하며 그림의 A, B, C ... 와 같은 동그라미를 말한다.

간선(Edge)은 링크(Link)라고도 하며 노드를 이은 선을 말한다. 화살표가 없으면 무뱡향 그래프, 화살표가 있으면 단방향/양방향 그래프가 된다.

가중치는 간선에 표시된 숫자이다. 있을수도 없을 수도 있다.

 

그래프의 특징

다수의 진입차수와 다수의 진출 차수를 가질 수 있고, 무방향성과 유방향성을 가질 수 있으며 순환과 비순환 형태를 가질 수 있다.

위에서 설명한 내용이다. 순환과 비순환은 추후에 설명하기로...

 

그래프 구현

• 인접행렬
• 인접리스트
• 간선리스트

세가지 방식으로 구현할 수 있다.

 

인접행렬

위에 첨부된 사진으로 예를 들었을 때 인접 행렬로 그래프의 정보를 나타낸다면 다음과 같이 표현할 수 있다.

	A	B	C	D	E
A	0	3	0	8	7
B	3	0	1	4	0
C	0	1	0	2	0
D	8	4	2	0	3
E	7	0	0	3	0

장점은 직관적이며 구현이 쉽다.

단점은 연결되지 않은 간선에 대해서도 저장하여 쓸모없는 메모리 발생.

 

인접리스트

연결된 노드만 저장한다.

A → B → D → E

B → A → C → D

C → B → D

D → A → B → C → E

E → A → D

정점의 개수만큼 인접리스트가 있고, 그 안에 연결된 노드 정보가 있다.

장점은 메모리 관리에 효율적

단점은 구현 어려움

하지만 알고리즘을 풀다보면 점점 인접리스트로 구현하게 된다.

 

그래프 알고리즘

• DFS : 출발점과 도착점의 모든 경로를 탐색
• 정점의 최단거리 알고리즘
  • 단일 출발점
    • BFS : 가중치가 없음
    • Dijkstra : 가중치 있음. 음의 가중치 없음
    • Bellman-ford : 가중치 있음. 음의 가중치 있음
  • 모든 출발점
    • Floyd warshall

 

	DFS	BFS	Dijkstra	Bellman-ford	Floyd warshall
방식	연결 정점 선택 후 끝날때까지 파고 들어가며 탐색	연결된 주변 정점 퍼져나가듯 탐색	한 정점에서 다른 정점까지의 최소 가중치 탐색	(수정중)	모든 정점에서 각 정점까지의 최소 가중치 탐색
자료구조	Stack / recursive	Queue	heap	(수정중)	3중 for문
시간복잡도	인접행렬 O(V^2) 인접리스트 O(V+E)		O(V^2) 힙 사용 O(ElogV)	(수정중)	O(V^3)

 

...

 

Floyd warshall 알고리즘

모든 정점에서의 최단 경로(가중치)를 구하는 알고리즘

음의 가중치, 양의 가중치 모두 사용 가능하다.

동작 과정

1. 그래프의 최단 거리 테이블 갱신

2. n번째 노드를 거쳐 가는 경우에 대해 테이블 갱신

 

그래프의 최단 거리 테이블 갱신

i → j로 가는 방향에 가중치를 표시해줬고, 갈 수 없는 경우는 무한 값으로 설정했다. 자기 자신으로 가는 경우는 0이다.

 

n번째 노드를 거쳐 가는 경우

연결되어 갈 수 있는 경우에만 갱신해준다.

• 1번째 노드 A를 거쳐 가는 경우

A를 거쳐서 갈 수 있는 경우는 B → C의 경우만 존재한다. 갱신된 값을 비교하여 테이블을 갱신해준다

 

• 2번째 노드 B를 거쳐 가는 경우

D→B→A→C의 경우는

기존의 B→C 경로가 B→A→C 인 최단경로로 업데이트됐기 때문에 D→B→C 가 아닌 D→B→A→C가 된다.

 

• 3번째 노드 C를 거쳐 가는 경우

마찬가지로 BCD의 경우도 BACD로 갱신된다.

 

• 4번째 노드 D를 거쳐 가는 경우

CDB를 새로 연결해준다

CDB가 갱신되었기 때문에 CDBA의 새 경로를 업데이트해줄 수 있다.

 

AD는 위에서 연결이 새로 갱신되었기 때문에 ACDB로 갱신해줄 수 있다.

최종적으로 위와 같은 최단거리 그래프가 나오게 된다.

 

의사코드

let dist be V × V matrix of minimum distances initialized to INFINITY
for each vertex v
  dist[v][v] = 0
for each edge (u, v)
  dist[u][v] = weight(u, v)
 
for k from 0 to |V| – 1
  for i from 0 to |V| – 1
    for j from 0 to |V| – 1
      if (dist[i][k] + dist[k][j]) is less than dist[i][j] then
        dist[i][j] = dist[i][k] + dist[k][j]

초기값을 INF로 초기화해준다.

자기 자신에 대해서는 0으로, 간선이 존재하면 가중치로 갱신해준다.

 

거쳐가는 노드를 k로 두고 노드만큼 반복한다.

i는 시작하는 노드, j는 도착하는 노드이고 각각 노드의 수만큼 반복해준다..

만약 현재 i, j의 연결보다 k를 거쳐가는 경우가 더 작다면 갱신해준다.

 

구현은 셀프 ^-^

 

풀어보면 좋은 문제

백준 11404 플로이드 - 골드4

https://www.acmicpc.net/problem/11404