RUBY

[이론] 그래프 이론 본문

PS/This

[이론] 그래프 이론

RUBY_루비 2020. 8. 8. 15:24
그래프

: 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조 

- 알고리즘 문제에서 '서로 다른 대체(객체)'가 연결되어 있다' => 그래프 알고리즘 을 떠올려야한다

- 구현 방법)

  1. 인접행렬 : 2차원 배열을 사용하는 방식

   - O(V^2)만큼의 메모리 공간 필요

   - 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용을 O(1) 의 시간으로 알 수 있다. 

  2. 인접리스트: 리스트를 사용하는 방식 

   - O(E) 만큼의 메모리 공간 필요 

  - 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용을 O(V) 의 시간으로 알 수 있다. 

 

 

서로소 집합(Disjoint Sets)

: 서로소 집합이란 공통 원소가 없는 두 집합을 의미 ex) {1,2}, {3,4}

 

* 서로소 집합 자료구조(union - find) 

: 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조

- union-find 로 조작할 수 있음

- union 연산: 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산

- find 연산: 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 

- 각 집합이 어떤 원소를 공통으로 가지고 있는지를 확인할 수 있다는 말과 같다

- 알고리즘)

  1. union 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인한다.

   1-1) A와 B의 루트노드 A', B' 를 각각 찾는다

   1-2) A' 를 B' 의 부모 노드로 설정한다(B'가 A'를 가리키도록 한다)

  2. 모든 union 연산을 처리할 때까지 1번 과정을 반복한다

 

- 기본적인 서로소 집합 알고리즘 소스코드

 :find함수가 비효율적으로 동작한다. 최악의 경우, find 함수가 모든 노드를 다 확인하는 터라 시간 복잡도가 O(V)라는 점이다 

 - 노드의 개수가 V개 이고 find 혹은 union 연산의 개수가 M개 일 떄, 전체 시간복잡도는 O(VM)이 되어 비효율적이다. '

#기본적인 서로소 집합 알고리즘 소스코드
#
import sys
sys.stdin = open("input.txt","r")

#특정 원소가 속한 집합을 찾기
def find_parent(parent,x):
    #루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] !=x:
        return find_parent(parent,parent[x])
    return x

#두 원소가 속한 집합을 합치기
def union_parent(parent,a,b):
    a=find_parent(parent,a)
    b=find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b

#노드의 개수와 간선(union 연산)의 개수 입력받기
v,e =map(int,input().split())
parent=[0]*(v+1) #부모 테이블 초기화

#부모 테이블상에서,부모를 자기 자신으로 초기화
for i in range(1,v+1):
    parent[i]=i

#union연산을 각각 수행
for i in range(e):
    a,b=map(int,input().split())
    union_parent(parent,a,b)

#각 원소가 속한 집합 출력
print('각 원소가 속한 집합: ', end=' ')
for i in range(1,v+1):
    print(find_parent(parent,i),end=' ')
print()

#부모 테이블 내용 출력
print('부모 테이블:',end=' ')
for i in range(1,v+1):
    print(parent[i],end=' ')

 

- 개선된 서로소 집합 알고리즘 소스코드

 : 경로 압축 방법 만을 이용할 경우의 시간복잡도는 노드의 개수가 V이고, 최대 V-1개의 union연산과 M개의 find 연산이 가능할 때 경로 압축 방법을 적용한 시간복잡도는

#개선된 서로소 집합 알고리즘 소스코드
#
import sys
sys.stdin = open("input.txt","r")

#특정 원소가 속한 집합을 찾기
def find_parent(parent,x):
    #루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] !=x:
        parent[x]= find_parent(parent,parent[x])
    return parent[x]

#두 원소가 속한 집합을 합치기
def union_parent(parent,a,b):
    a=find_parent(parent,a)
    b=find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b

#노드의 개수와 간선(union 연산)의 개수 입력받기
v,e =map(int,input().split())
parent=[0]*(v+1) #부모 테이블 초기화

#부모 테이블상에서,부모를 자기 자신으로 초기화
for i in range(1,v+1):
    parent[i]=i

#union연산을 각각 수행
for i in range(e):
    a,b=map(int,input().split())
    union_parent(parent,a,b)

#각 원소가 속한 집합 출력
print('각 원소가 속한 집합: ', end=' ')
for i in range(1,v+1):
    print(find_parent(parent,i),end=' ')
print()

#부모 테이블 내용 출력
print('부모 테이블:',end=' ')
for i in range(1,v+1):
    print(parent[i],end=' ')

 

 

- 서로소 집합을 활용한 사이클 판별

 - 서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다

 - union연산은 그래프에서의 간선으로 표현될 수 있다

 - 알고리즘

  1. 각 간선을 확인하며 두 노드의 루트 노드를 확인한다

    1-1) 루트 노드가 서로 다르다면 두 노드에 대하여 union연산을 수행한다

    1-2) 루트 노드가 서로 같다면 사이클이 발생한 것이다

  2. 그래프에 포하되어 있는 모든 간선에 대하여 1번과정을 반복한다. 

 - 사이클 판별 알고리즘은 그래프에 포함되어 있는 간선의 개수가 E개 일 때 모든 간선을 하나씩 확인하며 , 매 간선에 대하여 union 및 find 함수를 호출하는 방식으로 동작한다. 

#서로소 집합을 활용한 사이클 판별 소스코드
#
import sys
sys.stdin = open("input.txt","r")

#노드의 개수와 간선의 개수 입력받기
v,e=map(int,input().split())
parent=[0]*(v+1) #부모 테이블 초기화

def find_parent(parent,x):
    if parent[x]!=x:
        parent[x]=find_parent(parent,parent[x])
    return parent[x]

def union_parent(parent,a,b):
    a=find_parent(parent,a)
    b=find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b

#부모 테이블 상에서 자기 자신 초기화
for i in range(1,v+1):
    parent[i]=i

cycle=False

for i in range(e):
    a,b=map(int,input().split())
    #사이클이 발생한 경우 종료
    if find_parent(parent,a)==find_parent(parent,b):
        cycle = True
        break
    #사이클이 발생하지 않았다면 union
    else:
        union_parent(parent,a,b)
if cycle:
    print("사이클이 발생했습니다")
else:
    print("사이클이 발생하지 않았습니다")

 

 

신장 트리(Spanning Tree)

: 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

 

* 크루스칼 알고리즘

: 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 최소 신장 트리 알고리즘이라고 하는데 대표적인 최소 신장 트리는 크루스칼 알고리즘

- 그리디 알고리즘

- 알고리즘)

 1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다

 2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다

   2-1) 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다

   2-2) 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.

 3. 모든 간선에 대하여 2번의 과정을 반복한다

- 간선의 개수가 E개 일 때, O(ElogE) 의 시간복잡도를 가짐, 크루스칼 알고리즘에서 시간이 가장 오래 걸리는 부분이 간선을 정렬하는 작업이며, E개의 데이터를 정렬했을 떄의 시간복잡도가 O(ElogE)이기 때문에 

- 크루스칼 내부에서 사용되는 서로소 집합 알고리즘의 시간 복잡도는 정렬 알고리즘의 시간 복잡도 보다 작으므로 무시한다

#크루스칼 알고리즘
#
# 
'''
입력
7 9
1 2 29
1 5 75
2 3 35
2 6 34
3 4 7
4 6 23
4 7 13
5 6 53
6 7 25
출력
159
'''
import sys
sys.stdin = open("input.txt","r")

#노드의 개수와 간선의 개수 입력받기
v,e=map(int,input().split())
parent=[0]*(v+1) #부모 테이블 초기화

#모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges=[]
result=0

#부모 테이블 상에서, 부모를 자시 자신으로 초기화
for i in range(1,v+1):
    parent[i]=i

#모든 간선에 대한 정보를 입력받기
for _ in range(e):
    a,b,cost=map(int,input().split())
    #비용순으로 정렬하기 위해서 튜플의 첫 번쨰 원소를 비용으로 설정
    edges.append((cost,a,b))

#간선을 비용순으로 정렬
edges.sort()

def find_parent(parent,x):
    if parent[x]!=x:
        parent[x] = find_parent(parent,parent[x])
    return parent[x]

def union_parent(parent,a,b):
    a=find_parent(parent,a)
    b=find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b

#간선을 하나씩 확인하며
for edge in edges:
    cost,a,b=edge
    #사이클이 발생하지 않는 경우에만 집합에 포함
    if find_parent(parent,a) != find_parent(parent,b):
        union_parent(parent,a,b)
        result+=cost

print(result)

 

* 위상 정렬

: 위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘으로 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것

 ex) 선수과목 : 자료구조 -> 알고리즘 -> 고급 알고리즘

- 알고리즘

  1. 진입차수가 0인 노드를 큐에 넣는다

  2. 큐가 빌 때까지 다음의 과정을 반복한다

    2-1) 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다

    2-2) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다

 

 - 시간복잡도 O(V+E) , 위상정렬을 수행할 때는 차례대로 모든 노드를 확인하면서, 해당 노드에서 출발하는 간선을 차례대로 제거해야한다. 노드와 간선을 모두 확인한다는 측면에서 시간복잡도가 나온다. 

#위상정렬
#
'''
7 8
1 2
1 5
2 3
2 6
3 4
4 7
5 6
6 4
#출력
1 2 5 3 6 4 7 
'''
import sys
from collections import deque
sys.stdin = open("input.txt","r")

#노드의 개수와 간선의 개수를 입력받기
v,e=map(int,input().split())
indegree=[0]*(v+1)

graph=[[] for i in range(v+1)]

#방향 그래프의 모든 간선 정보를 입력받기
for _ in range(e):
    a,b=map(int,input().split())
    graph[a].append(b) #정점 A에서 B로 이동 가능
    #진입차수를 1증가
    indegree[b]+=1

#위상정렬 함수
def topology_sort():
    result = []
    q=deque()

    #처음 시작할 떄는 진입차수가 0인 노드를 큐에 삽입
    for i in range(1,v+1):
        if indegree[i]==0:
            q.append(i)
    #큐가 빌때까지 반복
    while q:
        now=q.popleft()
        result.append(now)
        #해당 원소와 연결된 노드들의 진입차수에서 1빼기
        for i in graph[now]:
            indegree[i]-=1
            #새롭게 진입차수가 0이 되는 노드를 큐에 삽입
            if indegree[i]==0:
                q.append(i)

    #위상정렬을 수행한 결과
    for i in result:
        print(i,end=' ')
topology_sort()

 

저작자표시 비영리 변경금지

'PS > This' 카테고리의 다른 글

팀 결성  (0) 2020.08.10
미래 도시  (0) 2020.08.10
[이론] 최단 경로  (0) 2020.08.06
효율적인 화폐 구성  (0) 2020.08.06
개미 전사  (0) 2020.08.06
'PS/This' Related Articles more
Comments