[SW Expert Academy] Advanced-6 그래프의 기본과 탐색
그래프는 평소에 잘 접하지 않기 때문에, 더욱 튼튼히 공부할 필요가 있다.
플로우 1.그래프의 기본 2. 그래프 탐색(DFS, BFS) 3. 상호배타 집합 (서로소)
1. 그래프
- 객채들과 이들 사이의 연결 관계를 표현한 것
-Vertex의 집합과, 이들을 연결하는 Edge들의 집합으로 구성된 구조
G = (V, E) // V:정점들의 집합, E: 간선들의 집합
|V|개의 정점을 가지는 그래프의 최대 간선 수 : V-1 + V-2 + ... + V-V = |V|*|V-1|/2
그래프 표현 방법
1) 인접 행렬 (Adjacent Matrix)
-> |V|*|V|개의 2차원 배열을 이용하여 간선 정보를 저장
-단점
->메모리 크기 |V|^2으로, 정점의 갯수가 커지면 공간 소모가 크다.
->어떤 정점의 인접 정점을 조사하는데 걸리는 시간이 O(|V|)
->따라서 정점의 갯수에 비례하여 시간도 증가한다.
2) 인접 리스트 (Adjacent List)
->각 정점마다 인접 정점으로 나가는 간선의 정보 저장
-장점
->불필요한 메모리 사용 절감 O(|V|+|E|)
->어떤 정점을 인접 정점을 찾는데 걸리는 시간 = 정점의 차수
3) 간선의 배열
->간선(시작 정점, 끝 정점)을 배열에 연속적으로 저장
->정점의 갯수에 비해 간선의 수가 적을 경우 사용
2. 그래프 탐색 (DFS, BFS)
1)DFS
-수도코드
DFS_Recursie(G, v):
visited[v] <- True
for all w in ADJ(v):
if visited[w] != True:
DFS_Recursive(G, w)
DFS_Iterative(S, v):
push(S, v)
while S is not empty:
v = pop(S)
if visited[v] == False:
visited[v] = True
for all w in ADJ(G,v):
if visited[w] == False:
push(S, w);
2)BFS
-수도 코드
BFS(Q, v):
enqueue(Q, v)
visited[v] = True
while Q is not empty:
v = dequeue(Q, v)
for each w in ADJ(G, v):
if visited[w] == False:
enqueue(Q, w)
visited[w] = True
-BFS를 이용한 시작 정점에서의 최단 경로 확인하기
//D[]: 최단 거리, P[]: 최단 경로 (최단 경로 중 바로 이전 노드)
BFS(G, Q, v):
D[v] = 0, P[v] = v
enqueue(Q, v)
visited[v] = True
while Q is not empty:
v = dequeue(Q)
for each w in ADJ(G, v):
if visited[w] = False:
enqueue(Q, w)
visited[w] = True
D[w] = D[v]+1
P[w] = v
->DFS는 스택(LIFO)구조라서, Recursive 함수 또는 스택을 이용하여 구현이 가능하다.
여기서 DSF_Iterative의 visited의 위치를 주의할 필요가 있다.
BFS와 달리 노드가 push할떄가 아니라, pop할때 visited를 1로 표기한다.
스택은 Last Input First Output이기 떄문에, push할떄 visited를 표기해버리면, Last input에 실패하기 때문이다.
그러면, 완전 순회는 가능하지만, 순회 순서가 바뀌어버린다.
이와 반면, BFS은 First Input First Output이기 떄문에, push할떄 visited를 표기해서, queue의 size를 최소화하고 시간을 줄인다.
->BFS의 최단 경로는 가중치가 없는 그래프에 적용 가능하다.
BFS는 기본적으로 가까운 경로부터 방문하여 탐색하기 때문에, 자연스럽게 방문하는 각 노드가 최단 지점이 되기 때문이다.
주의할 점은 최단 경로를 저장하는 P[]이다.
최단 경로를 지정한다면, 나였으면 각 노드마다 모든 과거 경로를 저장할텐데, 그럴 필요가 없다.
각 노드의 "이전 노드"만 저장한다면, P의 경로 순회를 통해 최단 경로를 구할 수 있기 떄문이다.
메모리공간을 크게 줄일 수 있다.
3. 상호배타 집합 (서로소)
-서로 중복 포함된 원소가 없는 집합의 관계를 서로소라 한다.
-중복된 원소가 없기 떄문에, 각 집합의 한 원소를 대표자(Representative)로 볼 수 있다.
-크게 3가지의 연산이 있다.
1) Make-set
-원소 x만으로 구성된 집합을 생성하는 연산
2) Find-set
-임의의 원소 x가 속한 집합을 알아내기 사용한다. 집합의 대표자를 알기 위한 연산임
3) Union
-원소 x가 속한 집합과 원소 y가 속한 집합이 하나의 집합으로 합쳐지는 연산
-x,y는 대표자여야함
-새로운 집합은 임의의 원소를 대표자로 선택
-표현
1) 연결 리스트 표현
->같은 집합의 원소들을 하나의 연결 리스트로 관리한다.
->연결 리스트의 첫번쨰 원소를 대표자로 삼는다.
->각 노드는 대표 원소를 가리키는 링크도 가진다.
Find-Set(e): 인자 노드가 링크를 통해 대표자 노드를 리턴하면 된다. O(1)
Union(a,b): 크기가 작은 집합을 큰 집합의 뒤에 붙인다. 뒤에 붙은 작은 집합의 모든 노드의 링크가 큰 집합의 대표자를 가리켜야 한다. O(|b|)
2) 트리 표현
->하나의 집합을 하나의 트리로 표현
->자식 노드가 부모 노드를 가리키며, 루트 노드가 대표자가 된다.
Make-Set(a): 노드가 자기 자신을 가리킨다.
Make-Set(x):
P[x] <- x
Union(a, b): 한 집합의 루트가 다른 집합의 루트를 가리킨다. 연결리스트보다 계산이 간단함
Union(x,y):
p[Find-Set(y)] <- Find-set(x)
Find-Set(a): 자식 노드가 부모노드로 거슬로 올라가며 루트까지 도달하여 리턴한다. (루트는 부모노드=자기자신인 것을 보고 알 수 있다.) O(|a|) <-최악의 경우 탐색 시간이 길어진다. (편향된 트리)
Find-set(x):
if x == p[x]: return x
else : return Find-Set(p[x])
->O(|a|) <-최악의 경우 탐색 시간이 길어진다. (편향된 트리)
->예를 들어, 노드의 수가 1개인 집합 아래로 다른 집합이 계속해서 union된다고 하자. 트리의 노드 수와 레벨이 같아져버린다.
->챌린지는 트리의 높이를 줄이는 것이다.
->해결책은 Rank, Path compression이 있다.
1)Rank를 이용한 Union
-각 노드는 자신을 루트로 하는 subtree의 높이를 Rank라는 이름으로 저장한다.
-두 집합을 합칠 때 rank가 낮은 집합을 rank가 높은 집합에 붙여서 트리의 레벨을 유지한다.
->집합이 합쳐질때
2)Path compression
-Find-Set과정에서 만나는 모든 노드들이 직접 root를 가리키도록 포인트를 바꾼다.
->최적화를 이용한 수도코드
Make-Set(x):
p[x] <- x
rank[x] <- 0
Find-Set(x):
if x != p[x]:
p[x] <- Find_Set(p[x]) //Find-set과정에서 지나는 모든 노드들의 부모 노드가 루트를 가리키도록 갱신한다.
return p[x]
Union(x, y):
Link( Find-Set(x), Find-Set(y))
Link(x, y):
if rank[x] > rank[y]:
p[y] <- x
else
p[x] <- y
if rank[x] == rank[y]:
rank[y]++
Reference
댓글
댓글 쓰기