2021-06-13-Algo-REVIEW

Graph Algo?

• graph 란 Node와 Node사이에 연결된 Edge 의 정보를 가지고 있는 자료구조

• 그래프 구현 방법은 2가지가 존재한다. (메모리와 속도 측면에서 다른 결과를 보임)
  • 인접행렬 : 2차원 배열을 사용하는 방식
  • 인접 리스트 : 리스트를 사용하는 방식

서로소 집합 (Disjoints Sets)

• 공통 원소가 없는 두 집합을 의미하는 자료구조 위 자료구조를 처리하기 위해서는 Union, Find 2개의 연산으로 처리해야한다.

1. Union

• 두 원소가 속한 집합을 합치는 함수

 private static void union(int a, int b){
        a=find(a);
        b=find(b);
        if(a<b) parent[b]=a;
        else parent[a]=b;
    }

2. Find

• x가 속한 집합의 대표값(루트 노드 값)을 반환한다. 즉, x가 어떤 집합에 속해 있는지 찾는 연산

[비대칭 트리구조]
private static int find(int x){
        if(x==parent[x]) return x; // 자기 자신의 루트 노드 라는 의미
        return find(parent[x]);
    }

비대칭 트리구조 형태일 경우 연결 리스트 형태로 구성되어 배열로 구현하는 방식보다 시간 복잡도가 O(N) 이 되어 비효율적인 구성이 된다.

시간 복잡도를 개선하기위해서는 리스트 형태의 트리 구조를 경로압축 과정을 통해 시간복잡도가 O(lonN) 인 균형있는 트리 구조로 개선해야한다.

[대칭 트리구조]
private static int find(int x){
        if(x==parent[x]) return x; // 자기 자신의 루트 노드 라는 의미
        return parent[x]=find(parent[x]);
    }

• 두 함수를 같이 구성하여 Union-find 알고리즘 과정을 표현할 수 있다. 이 과정으로 통해 크루스칼 알고리즘 을 표현할 수 있게 된다.

Union-Find 알고리즘의 무한 순회

• Union-Find 알고리즘을 구현할 경우 Find 함수에서 무한 순회가 발생할 경우 Union 함수를 수행할 수 없게 된다. Cycle 판단하는 함수를 구성하여 자기자신의 노드를 마주했을 때 함수를 빠져 나가 Union 함수를 수행하도록 해야한다.

  boolean cycle = false;
  
  for(int i=1; i<=e; i++){
  int a= sc.nextInt();
  int b = sc.nextInt();
  if(find(a)==find(b)){
   cycle = true;
   break;
   }
   else
  union(a,b);
  }

최소한의 비용으로 모든 노드를 순회(Kruskal Algorithm)

크루스칼 알고리즘은 신장트리 자료구조를 기반으로 하며 작은 비용으로 모든 노트를 순회를 목적으로 한다. 이때 시간 복잡도는 O(ElogE) 이다.

( 신장트리 : 하나의 크래프가 존재할 때 모든 노드를 포함하면서 사이클이 존재하지 않는 그래프)

1. 간선의 크기에 따라 오름차순 정렬
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생하는지 판단(Union-Find Algorithm)
3. 모든 간선에 대해 2번의 과정을 반복

🙆‍♂ 예시 코드 링크

• Union-Find Algorithm
• [Union-find Cycle Algorithm]()
• [Kruskal Algorithm]()

🧾 Reference

• 이것이 코딩 테스트다 whit Python
• Union-Find 알고리즘