우주의WouldYou

출처: www.youtube.com/watch?v=aOhhNFTIeFI&t=1307s

<위상 정렬>

- 사이클이 없는 방향 그래프(DAG)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것

(*사이클이 있으면 모든 노드의 진입 차수가 1이상이 됨 -> 위상정렬 수행 불가)

[진입 차수와 진출 차수]

- 진입차수(Indegree): 특정한 노드로 들어오는 간선의 개수

- 진출차수(Outdegree): 특정한 노드에서 나가는 간선의 개수

[위상 정렬 알고리즘]

- 큐를 이용(dfs를 이용해서도 가능)

[위상 정렬의 특징]

- DAG에 대해서만 수행 가능

- 여러 가지 답이 존재할 수 있다

    : 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우

- 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단

- 스택을 활용한 DFS를 이용해 위상 정렬을 수행할 수도

from collections import deque

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로 이동
    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()

int v, e; //노드 개수, 간선 개수
int indegree[100001]; 진입차수
vector<int> graph[100001]; //간선정보 연결 리스트

void topologySort(){
    vector<int> result;
    queue<int> q;
    
    for(int i= 1; i <= v; i++){
        if( indegree[i] == 0)
            q.push(i);
    }
    
    while(!q.empty()){
        int now = q.front();
        q.pop();
        result.push_back(now);
        for(int i= 0 ; i < graph[now].size(); i++){
            //해당 원소와 연결된 노드들의 진입차수에서 1 빼기
            indegree[graph[now][i]] -=1;
            //새롭게 진입차수가 0이 되는 노드를 큐에 삽입
            if(indegree[graph[now][i]] == 0){
                q.push(graph[now][i]);
            }
        }
    }
    
    for(int i=0 ; i< result.size(); i++){
        cout << result[i] <<" " ;
    }
}
    

[위상 정렬 알고리즘 성능 분석]

- 위상 정렬을 위해 차례대로 모든 노드를 확인하며 각 노드에서 나가는 간선을 차례대로 제거해야 함

    : 위상 정렬 알고리즘의 시간 복잡도는 O(V+E)

출처: www.youtube.com/watch?v=aOhhNFTIeFI&t=1307s

<신장 트리>

- 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 의미

    : 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건 == 트리의 조건

- 모든 노드가 연결되어 있지만 일부 간선을 사용하지 않아도 괜찮다

<최소 신장 트리>

- 최소한의 비용으로 구성되는 신장 트리

    ex) N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우

    : 두 도시 A, B를 선택했을 때 A에서 B로 이동하는 경로가 반드시 존재하도록 도로 설치

<크루스칼 알고리즘>

- 대표적인 최소 신장 트리 알고리즘

- 그리디 알고리즘으로 분류

[동작 과정]

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(a)
    b = find_parent(b)
    if a< b:
        parent[b] = a
    else:
        parent[a] = b
        
 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()

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) #간선 비용의 합

int v, e;
vector<pair<int, pair<int, int>> edges;
int result = 0;

int findParent(int x){
    if(x == parent[x]) return x;
    return parent[x] = findParent(parent[x]);
}

void unionParent(int a, int b){
    a = findParent(a);
    b = findParent(b);
    if (a<b) parent[b] = a;
    else parent[a] = b;
}
int main(){
    for(int i=1 ;i <=v; i++)
        parent[i] = i;
    for(int i=0; i < e; i++){
        int a, b, cost;
        cin >> a>> b>> cost;
        edges.push_back({cost, {a, b}});
    }
    
    sort(edges.begin(), edges.end());
    
    for(int i=0; i < edges.size(); i++){
        int cost = edges[i].first;
        int a = edges[i].second.first;
        int b = edges[i].second.second;
        
        if(findParent(a) != findParnet(b)){ //사이클 발생 x경우만
            unionParent(a, b);
            result += cost;
        }
    }
    cout << result;
}
        
    

[성능 분석]

- 간선의 개수가 E개일 때, O(ElogE)의 시간 복잡도를 가짐

- 가장 많은 시간을 요구하는 곳 => 간선의 정렬을 수행하는 부분

    :표준 라이브러리를 이용해 E개의 데이터를 정렬하기 위한 시간 복잡도는 O(ElogE)

출처:www.youtube.com/watch?v=aOhhNFTIeFI

<서로소 집합 자료구조>

- 서로소 집합(Disjoint Sets)란 공통 원소가 없는 두 집합을 의미

ex. {1,2}와 {3,4}는 서로소 관계이고, {1,2}와 {2,3}은 서로소 관계가 아니다.

- 서로소 판별을 위해 사용할 수 있는 자료구조

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

- 서로소 집합 자료구조는 두 종류의 연산을 지원

    1. 합집합(Union): 두 개의  원소가 포함된 집합을 하나의 집합으로 합치는 연산

    2. 찾기(Find): 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

- 서로소 집합 자료구조는 합치지 찾기(Union Find) 자료구조라고 불리기도 함

[여러 개의 합치기 연산이 주어졌을 때 서로소 집합 자료구조의 동작과정]

1. 각각의 합치기(Union)연산을 확인하여, 서로 연결된 두 노드 A, B를 확인

    1) A와 B의 루트 노드들을 각각 찾는다.

    2) 해당 루트노드들을 부모 노드로 설정

2. 모든 합집합(Union)연산을 처리할 때까지 1번의 과정을 반복

[서로소 집합 자료구조: 연결성]

- 기본적인 형태의 서로소 집합 자료구조에서는 루트 노드에 즉시 접근할 수 없음

     : 루트 노드를 찾기 위해 부모 테이블을 계속해서 확인하며 거슬러 올라가야 한다.

#Python Union Find


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 =' ')

int v, e; //노드의 개수(v)와 간선(union 연산)의 개수(e)
int parent[100001];

int findParent(int x){ //특정 원소가 속한 집합 찾기
    if (x == parent[x]) return x;
    return findParent(parent[x])
}

void unionParent(int a, int b){ //두 원소가 속한 집합을 합치기
    a = findParent(a)
    b = findParent(b)
    if (a<b) parent[b] = a;
    else parent[a] = b;
}
int main(){
    cin >> v >> e;
    for(int i= 1; i <=v; i++){
        parent[i] = i;
    }
    
    //union연산 수행
    for(int i=0; i <e; i++){
        int a,b;
        cin >> a>> b;
        unionParent(a, b);
    }
    
    //각 원소가 속한 집합 출력
    cout << "각 원소가 속한 집합: ";
    for(int i = 1; i <=v; i++){
        cout <<findParent(i) <<" ";
    }
    
    //부모 테이블 출력
    cout >> "부모 테이블: " ;
    for(int i= 1; i <=v; i++){
        cout << parent[i] <<" ";
    }
}

[기본적인 구현 방법의 문제점]

- 합집합(Union)연산이 편향되게 이루어지는 경우 찾기(Find)함수(매번 부모 테이블을 참조, 부모에 대해 재귀적 호출) 가 비효율적으로 동작함

- 최악의 경우에는 찾기(Find)함수가 모든 노드를 다 확인하게 되어 시간 복잡도가 O(V)

-> 경로 압축!!

[경로 압축]

- 찾기(Find)함수를 최적화하기 위한 방법으로 경로 압축(Path Compression)을 이용할 수 있음

    : 찾기(Find)함수를 재귀적으로 호출한 뒤에 부모 테이블 값을 바로 갱신

def find_parent(parent, x):
    if parent[x] != x: #루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적 호출
        parent[x] = find_parent(parent,  parent[x])
    return parent[x]

int findParent(int x){
     if(x == parent[x]) return x;
     return parent[x] = findParent(parent[x]);
}

- 경로 압축 기법을 적용하면 각 노드에 대하여 찾기(Find)함수를 호출한 이후에 해당 노드의 루트 노드가 바로 부모 노드가 됨

- 모든 합집합(Union)함수를 처리한 후 각 원소에 대하여 찾기(Find)함수를 수행

- 시간 복잡도 개선

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

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

   : 참고로 방향 그래프에서의 사이클 여부는 DFS를 이용하여 판별할 수 있음

- 사이클 판별 알고리즘

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

        1) 루트 노드가 서로 다르다면 두 노드에 대하여 합집합(Union) 연산을 수행

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

     2. 그래프에 포함되어 있는 모든 간선에 대해 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
        
        
# 노드의개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().split())
parent  = [0] * (v+1) #부모 테이블 초기화

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

cycle = False #사이클 발생 여부

#union연산을 각각 수행
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("사이클 발생 x")

출처: www.youtube.com/watch?v=acqm9mM1P6o&t=374s

<플로이드 워셜 알고리즘>

- 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산

- 다익스트라와 마찬가리고 단계별로 거쳐가는 노드를 기준으로 알고리즘 수행

    : 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 찾는 과정은 필요하지 않음

- 플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장(3중 반복문을 통해 갱신)

- 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속함

- 구현 난이도는 다익스트라에 비해 쉬움

- 시간 복잡도가 높으므로 노드의 개수가 적은 경우에만 사용

- 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인(이를 이용해 테이블 갱신)

    : a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사

- 점화식

1. 그래프 준비, 최단 거리 테이블초기화

2. 이중 반복문,  k번 노드를 거쳐가는 경우를 고려하여 테이블 갱신

총 3중 반복문을 사용하게 됨

#Python
INF= int(1e9) #무한(10억)

#노드의 개수 및 간선의 개수
n = int(input())
m = int(input())

#2차원 리스트(그래프 표현)을 만들고, 무한으로 초기화
graph = [[INF] * (n+1)for _ in range(n+1)]

#자기 자신에서 자기 자신으로 가는 비용 0으로 초기화
for a in range(1, n+1):
    for b n range(1, n+1):
       if a==b:
            graph[a][b] = 0
            
            
#각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
for _ in range(m):
    #a에서 b로가는 비용은 c라고 설정
    a, b, c = map(int, input().split())
    graph[a][b] = c

#점화식에 따라 플로이드 워셜 알고리즘 수행
for k in range(1, n+1):
    for a  in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

#수행된 결과 출력
for a in range(1, n+1):
    for b in range(1, n+1):
        #도달할 수 없는 경우, 무한(infinity)출력
        if graph[a][b] == INF:
            print("Infinity", end=" ")
        #도달할 수 있는 경우, 거리 출력
        else:
            print(graph[a][b], end= " ")
    print()

#define INF 1e9

int n, m;
int graph[501][501]; //플로이드 워샬을 사용해여 하는 경우 노드가 500개 이상 되는 경우가 거의 없음(3중 for문이라)

int main(){
    cin >> n >> m;
    
    //최단 거리 테이블을 모두 무한으로 초기화
    for (int i = 0;i < 501; i++){
         fill(graph[i], graph[i] + 501,INF);
    }
    
    //자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
    for(int a = 1; a <= n; i++){
        for(int b = 1; b <= n; b++){
            if(a==b) graph[a][b] = 0;
        }
    }
    
    //점화식에 따라 플로이드 워셜 알고리즘 수행
    for(int k =1; k <=n; k++){ //거쳐가는 노드
        for(int a =  1; a<=n; a++){ //출발 노드
            for(int b = 1; b<=n; b++){ //도착 노드
                graph[a][b] = min(graph[a][b], graph[a][k]+ graph[k][b]);
            }
        }
    }
    
    //수행 결과
    for(int a = 1; a<=n; a++){
        for(int b= 1; b<=n; b++){
            if(graph[a][b] == INF) cout << "Infinity" <<endl;
            else cout << graph[a][b] <<endl;
        }
    }
}
    
    

노드의 개수 N개 -> N번의 단계 수행 -> 각 단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐가는 모든 경록 ㅗ려

총 시간 복잡도는 O(N^3)