공부하는블로그

라빈카프 문자열 매칭

  해시(Hash)를 활용하는 알고리즘이며 평균적으로 O(N+M)의 시간 복잡도를 갖는 알고리즘이다.

  아스키코드 기반의 해시함수를 이용하여 특정한 문자열에 대한 해시값을 구한다.

  연속적인 문자열이 이어지는 상황이므로 해시함수의 동작에 있어서 연산속도가 O(1)이다.

  라빈카프 문자열 매칭 알고리즘에서 해시함수는 각 문자의 아스키코드값에 2의 제곱수를 차례대로 곱하여

  더한값을 구한다. 일반적으로 서로 다른 문자열의 경우 일반적으로 해시값이 다르게 나온다.

  해시함수에 기반한다는 점에서 해시충돌에 대한 처리가 필요하다.

  때에 따라서는 KMP알고리즘보다 빠르게 동작하기도 하지만 특정한 상황에서는 KMP알고리즘보다

  매우 느리게 동작할 수 있다.

해시함수 눈사태효과

  문자열 abacdab가 있다고 했을 때 이것은 12,380이라는 해시값을 갖는데

  = 97 * 2^6 + 98 * 2^5 + 97 * 2^4 + 100 * 2^2 + 97 * 2^1 + 98 * 2^0

  = 12,380

  이렇게 해시값이 나온다.

  a는 아스키코드값으로 97이다. 제곱수는 제일 오른쪽에 있는 값에 0제곱부터 올라오는데

  아스키코드값에 2의 제곱수를 곱한 값을 다 더한 값이 해시값이 된다.

  여기서 abacdab가 bbacdab로 변한다면 12,444로 해시값이 변하게 되는데 이것을 눈사태 효과라고 한다.

  이러한 눈사태 효과 때문에 서로 다른 문자열은 해시값이 서로 다르게 되는데 이 원리를 이용해서

  문자열 매칭을 수행하게 된다.

처리과정

  라빈카프 문자열매칭 알고리즘에서는 해시 충돌을 감안해야 한다는 점에서 부분 문자열의 해시값이 일치하는

  경우에만 문자열을 재검사한다.

  부모해시값 : 12,398

  패턴해시값 : 12,380

  여기서 부모해시값과 패턴 해시값이 동일하지 않으므로 부모문자열을 한칸 이동한다.

  부모해시값 : 12,477

  패턴해시값 : 12,380

  부모해시값 : 12,380

  패턴해시값 : 12,380

  반복해서 이렇게 해시값이 동일하다면 매칭이 발생한 것이다.

  부모해시값 : 12,441

  패턴해시값 : 12,380

  부모해시값 : 12,437

  패턴해시값 : 12,380

  이렇게 한칸씩 이동하면서 매번 부모해시값과 패턴해시값을 비교한다음 다시 앞부분부터 차근차근

  모든 문자가 동일하지 확인하는 방식으로 문자열 매칭 여부를 확인한다.

  결과적으로 부모문자열에서 한번만 발생했다고 판단할 수 있는 것이다.

  해시함수를 반복적으로 계산할때는 부모 문자열에서 패턴문자열의 길이와 똑같은 크기로 한칸씩 이동하면서 해시값을

  확인한다고 했는데 그렇기 때문에 문자열이 이어진다는 특징을 따라갈 수 있는 것이다.

  여기서 한칸 이동하게 되면 결국 c, a, b, a, c, d 이 6자리는 그대로 사용된다는 특징이 있다.

  그래서 실제로 새로 다음 해시값을 구하는데에 있어서 시간 복잡도는 O(1)인것이다.

  다음 해시값은

  2 * (현재해시값 - 가장앞에 있는 문자의 수치) + 새문자의 수치

  이 연산으로 구할 수 있다.

  가장 앞에 있는 문자인 a는 97 * 2^6 = 6208이다.

  그리고 새로 들엉올 문자의 수치는 97 * 2^0 = 97이다.

  그럼 연산에 적용해보면 2 * (현재해시값(12,398) - 가장앞에 있는 문자의 수치(6208)) + 새문자의수치(97)

  이렇게 계산해주면 두번째 해시값인 12,477이라는 해시값이 나온다.

예제코드

#include <stdio.h>
#include <string.h>

char* parent = "acabacdabac";
char* pattern = "abacdab";

void check(char* parent, char* pattern, int start){
  //부모문자열에서 패턴문자열이 일치하는지 확인하는 함수
  //부모문자열과 패턴문자열의 해시값이 일치하는 경우에만 수행된다.
  //실제로 모든 문자가 다 일치하는지 확인하기 위해서 사용되는 함수다.
  //start는 해시값이 일치하기 시작한 인덱스
  int found = 1;
  int patternSize = strlen(pattern);
  
  for(int i = 0; i < patternSize; i++){
    if(parent[start + i] != pattern[i]){
      //부모문자열과 패턴문자열이 정확히 일치하는지 확인
      found = 0;
      break;
    }
  }
  if(found){
    printf("[인덱스 %d]에서 매칭 발생.\n", start + 1);
  }
}

void rabinkarp(char* parent, char* pattern){
  int parentSize = strlen(parent);
  int patternSize = strlen(pattern);
  int parentHash = 0, patternHash = 0, power = 1;
  //각 해시값을 0으로 초기화
  //power는 제곱승을 의미한다.
  
  for(int i = 0; i <= parentSize - patternSize; i++){
    if(i == 0){ //i가 0일때는 부모의 해시와 패턴의 해시값을 구하게 된다.
      for(int j = 0; j < patternSize; j++){
        parentHash = parentHash + parent[patternSize - 1 - j] * power;
        //뒤에서 앞으로 이동하면서 곱해나간다.
        //패턴문자열 : abacdab가 있는데
        //제일 뒤에 있는 b의 아스키코드값에 power를 곱한다.
        //제일 뒤에있는 문자는 2^0을 곱하니 1을 먼저 곱하게 되는것이다ㅣ.
        
        patternHash = patternHash + pattern[patternSize - 1 - j] * power;
        //parentHash와 마찬가지로 처리
        
        if(j < patternSize - 1){
          power = power * 2;
          //2제곱을 만들어주기위해 반복문이 한번 수행될때마다
          //2를 곱해서 제곱과 같은 형태로 유지하게 한다.
        }
      }
    }
    else{
      parentHash = 2 * (parentHash - parent[i - 1] * power) + parent[patternSize - 1 + i];
      //i가 증가했으니 부모문자열이 한칸 뒤로 넘어갔다는 의미이다.
      //다음 해시값을 구하는 연산인
      //2 * (현재해시값 - 가장앞에있는 문자수치) + 새문자수치 연산을 수행하는것
    }
    
    if(parentHash == patternHash){
      //두 해시값이 일치하는 경우에는 check로 값을 보내 모든 문자열이 일치하는지 확인
      check(parent, pattern, i);
    }
  }
}

int main(void){
  rabinkarp(parent, pattern);
  system("pause");
}

  [인덱스 3]에서 매칭발생   이라는 결과값을 확인할 수 있다.

레퍼런스

패스트캠퍼스 올인원 패키지 - 소프트웨어 베이직

단순비교 문자열 매칭

  단순비교 문자열 매칭 알고리즘은 두 문자열을 처음부터 끝까지 계속 비교하는 알고리즘이다.

  단순비교 문자열 매칭 알고리즘은 O(NM)의 시간 복잡도를 갖는다.

  문자열 A에서 문자열 B를 찾는 과정

    문자열 A : "ABCDEFG"

    문자열 B : "EF"

    이렇게 있다고 하면

    이러한 순서로 찾아 나가야 한다.

  단순비교 문자열 매칭 예제코드

#include <stdio.h>
#include <string.h>

char* parent = "ABCDEFG";
char* pattern = "EF";

int main(void){
  int parentSize = strlen(parent);
  int patternSize = strlen(pattern);
  
  for(int i = 0; i <= parentSize - patternSize; i++){
    int found = 1;
    
    for(int j = 0; j < patternSize; j++){
      if(parent[i + j] != pattern[j]){
        found = 0;
        break;
      }
    }
    
    if(found){
      printf("%d번째에서 찾았습니다.\n", i + 1);
    }
  }
  system("pause");
}

    5번째에서 찾았습니다 라는 결과값을 볼 수 있다.

    A를 1부터 시작한다고 봤을때 5번째이므로 + 1을 한 값으로 출력했기 때문이다.

KMP 문자열 매칭

  단순 문자열 매칭은 O(NM)의 시간 복잡도로 상당히 비효율적이다.

  KMP문자열 매칭 알고리즘을 활용하면 O(N + M)의 시간 복잡도로 문제를 해결할 수 있다.

  KMP알고리즘은 접두사와 접미사를 활용해 빠르게 문자열 매칭을 수행하는 알고리즘이다.

  접두사와 접미사가 일치하는지의 여부를 활용한다.

  특정한 부모 문자열에서 찾고자 하는 패턴문자열이 "abacdab"라고 한다면

  이때 각 길이에 따른 접두사와 접미사가 일치하는 최대 길이를 구한다.

  여기서 보면 세번째에 aba는 양끝에 a가 하나씩 일치하기 때문에 최대일치길이가 1이고

  마지막에는 양 끝에 ab가 일치하기 때문에 최대일치길이가 2가 된다.

  이렇게 하나의 텡이블을 매칭전에 먼저 구축을 해두어야 한다.

  테이블 만들기

    j = 0, i = 1로 설정하고 테이블을 만든다.

    pattern[j]와 pattern[i]가 일치하는지 반복적으로 확인한다.

    일치하는 경우 j에 1을 더한 뒤에 j의 인덱스를 table[i]에 삽입한다.

    일치하지 않는 경우 j++ 해준다.

    이렇게 j는 0부터 i는 1부터 시작하게 된다. 테이블의 맨 앞에는 0을 넣어주고 시작한다.

    그럼 인덱스 j와 i는 문자가 일치하지 않기 때문에 테이블에 0이 들어가고 i는 하나 증가한다.

    여기서는 j와 i가 a로 일치하므로 j를 하나 증가시키고 i에 증가한 j의 인덱스를 넣어준 뒤 i도 증가한다.

    여기서도 j와 i가 불일치한다.

    이럴경우 마지막으로 일치했던 순간까지의 인덱스로 j를 이동해 다시 검사한다.

    마지막으로 일치했던 순간은 table[j - 1]이다.

    마지막으로 일치했던 인덱스로 이동했지만 여기서도 일치하지 않으므로 0을 넣어주고 i를 증가시킨다.

    이번에도 j와 i는 일치하지 않으니 0을 넣어주고 i만 증가시킨다.

    여기서는 j와 i가 일치하므로 j를 하나 증가시키고 i에 j의 인덱스를 넣어준 뒤 i를 증가시킨다.

    이번에도 j와 i가 일치하므로 j를 증가시키고 i에 j의 인덱스를 넣어준다.

    i가 마지막 인덱스까지 확인했으므로 테이블 생성을 마무리한다.

  문자열 매칭 진행

    문자열 매칭을 진행할 때에도 불일치하는 경우 j를 마지막으로 일치했던 순간까지의 인덱스로 이동해 다시 검사한다.

    마지막 일치했던 순간은 table[j - 1]이다.

    문자열 매칭을 진행할때는 j와 i 모두 0에서 시작한다.

    일치하는 경우는 i와 j를 모두 증가시킨다.

    지금 i와 j가 모두 일치하므로 둘다 증가시켜준다.

    여기서는 일치하지 않으므로 j를 마지막으로 일치했던 인덱스로 돌려보낸다.

    여기서도 일치하지 않으니 i만 증가시킨다.

    다시 i와 j가 일치하니 둘다 증가시켜주고

    계속 동일하므로 i와 j를 같이 증가시키면서 체크해준다.

    그럼 이제 패턴 문자열의 끝에 도달했으므로 매칭에 성공했다는 것을 확인할 수 있는 것이다.

    매칭을 성공한 다음에는 테이블의 마지막값을 확인한다.

    테이블의 마지막값은 2인데

    이 두개가 일치했다는 여부가 테이블에서 확인한것이기 때문에

    table[j]로 이동해서 다시 검사한다.

    table[j]는 패턴 문자열에서 3번째 인덱스에 있으므로 j를 3번째 인덱스로 이동하고 i도 증가시켜 다시 검사한다.

    그럼 일치하므로 i와 j 둘다 증가시키고

    이번에도 i와 j가 동일하지만 i가 인덱스의 끝에 도달했기 때문에 종료하게 된다.

    그럼 여기서는 단 한번만 매칭이 발생한 사실을 알 수 있다.

  예제코드

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* parent = "acabacdabac";
char* pattern = "abacdab";

int* makeTable(char* pattern){ //테이블생성
  int patternSize = strlen(pattern); //패턴의 길이
  int* table = (int*)malloc(sizeof(int) * patternSize);
  //테이블의 길이는 패턴의 길이와 일치하기 때문에 이렇게 동적할당
  
  for(int i = 0; i < patternSize; i++){
    table[i] = 0; //0으로 전부 초기화
  }
  
  int j = 0;
  
  for(int i = 1; i < patternSize; i++){
    while(j > 0 && pattern[i] != pattern[i]){ //불일치 한다면
      j = talbe[j - 1];
    }
    
    if(pattern[i] == pattern[j]){ //패턴이 일치한다면
      table[i] = ++j;
    }
  }
  return table;
}

//KMP
void KMP(char* parent, char* pattern){
  int* table = makeTable(pattern); //테이블 생성
  int parentSize = strlen(parent); //모든 위치를 i가 검사해야하기 때문에 parentSize가 필요
  int patternSize = strlen(pattern);
  
  int j = 0;
  
  for(int i = 0; i < parentSize; i++){
    while(j > 0 && parent[i] != pattern[j]){ //불일치하는 경우
      j = table[j - 1];
    }
    
    if(parent[i] == pattern[j]){ //일치하는 경우
      if(j == patternSize - 1){
        printf("[인덱스%d]에서 매칭 성공\n", i - patternSize + 2);
        j = table[j];
      }
      else{
        j++;
      }
    }
  }
}

int main(void){
  KMP(parent, pattern);
  system("pause");
}

    [인덱스 3]에서 매칭성공  이라는 결과값을 확인할 수 있다.

레퍼런스

패스트캠퍼스 올인원 패키지 - 소프트웨어 베이직

인덱스트리

  인덱스트리는 세그먼트 트리에 비해 구현이 매우 간단하다는 특징이 있다.

  인덱스트리를 활용하여 구한 합을 구하는 과정도 O(logN)의 시간 복잡도를 갖는다.

  인덱스트리는 세그먼트 트리에 비해서 메모리 효율성이 높다.

처리과정

  인덱스트리는 특정한 숫자의 마지막비트를 구해서 처리한다.

  특정한 숫자의 마지막 비트 구하기

    A가 14라고 할때 A를 비트로 표현하면 다음과 같다.

    00000000 00000000 00000000 00001110

    그리고 이것을 2의 보수를 이용해 -A로 만들어 준다면

    11111111 11111111 11111111 11110010 이 된다.

    이 둘을 AND연산 처리한다면

    00000000 00000000 00000000 00001110

    11111111 11111111 11111111 11110010

    -----------------------------------------------

    00000000 00000000 00000000 00000010

    이렇게 되고 그럼 마지막 비트만이 남게 된다.

  이러한 마지막 비트를 이용해서 트리구조를 만들 수 있다.

  여기서 인덱스 16은 1-16의 구간합을 값으로 갖게 되고 15는 15를, 14는 13-14의 구간합을, 13은 13을

  12는 9-12의 구간합을 값으로 갖게 된다.

  12아래로도 같은 형태로 값을 갖게 되는데 각 인덱스에 대하여 마지막 비트를 '내가 저장하고 있는 값들의 개수'

  로 계산하는 것이다.

  마지막 비트를 이용해 처리하는데 12의 경우는 0000 1100이고 2의 보수로 처리하면 1111 0100이 된다.

  그럼 이 둘을 AND연산 한다면 0000 0100 이 되므로 마지막비트는 4가 된다.

  그럼 12는 4개의 구간의 합을 가질 수 있다는 것이고 12, 11, 10, 9의 합을 갖게 되는것이다.

  만약 1-13의 구간합을 구한다고 한다면

  이와같이 인덱스 8, 12, 13의 합을 구한다면 그게 1-13의 구간합과 같아진다.

  처리과정은 원하는 구간합의 마지막 인덱스인 13으로 가는데 그럼 13은 마지막비트가 1이기 때문에 13의 값

  하나만 갖게 된다. 마지막 비트가 1이었으니 아래로 하나만 내려가서 인덱스 12로 내려가게 되고

  12는 4의 마지막비트를 갖고 있으니 인덱스 13의 값과 12의 값을 더하고 4 낮은 인덱스 8로 이동한다.

  인덱스 8은 마지막비트가 8이니 1-8의 구간합을 갖고 있고 마찬가지로 13과 12를 더한값에 8의 값을 더해준다.

  그럼 원하는 구간의 시작값인 1의 값까지 모두 합했으니 1-13의 구간합이 나온다.

  특정 인덱스 수정

    수정할때는 마지막 비트만큼 구간을 뒤로 이동하며 값을 수정하면 된다.

    5를 수정한다면 5를 수정하고 마지막 비트가 1이기때문에 하나만 올라가 인덱스 6으로 넘어가 6을 수정한다.

    6은 마지막비트가 2이기 때문에 8로 이동해 8을 수정하고 8은 마지막비트가 8이니 16으로 올라가 수정해주면 된다.

예제코드

#include <stdio.h>
#define NUMBER 7

int tree[NUMBER];

int sum(int i){
  int res = 0; //결과정수
  while(i > 0 { //i가 감소하면서 반복
    res += tree[i];
    //마지막 비트만큼 빼면서 앞으로 이동
    
    i -= (i & -i);
    //마지막 비트를 구하는 연산
  }
  return res;
}

void update(int i, int dif){
  while(i <= NUMBER){
    tree[i] += dif;
    //마지막 비트만큼 더하면서 뒤로 이동
    
    i += (i & -i);
  }
}

//구간합 계산 함수
int getSection(int start, int end){
  return sum(end) - sum(start - 1);
  /*
    5-7의 구간합을 구하려고 한다고 했을 때
    1-7의 구간합을 구한 뒤
    1-4의 구간합을 빼주면
    5-7의 구간합과 같다.
  */
}

int main(void){
  update(1, 7); //트리의 1번 인덱스에 7이라는 값을 넣는다.
  update(2, 1);
  update(3, 9);
  update(4, 5);
  update(5, 6);
  update(6, 4);
  update(7, 1);
  printf("1부터 7까지의 구간합 : %d\n", getSection(1, 7));
  printf("인덱스 6의 원소를 +3만큼 수정\n");
  update(6, 3); //update는 그냥 값만 넣어주는 것이 아닌 += 이므로 +3이 되는것.
  printf("4부터 7까지의 구간합 : %d\n", getSection(4, 7));
  system("pause");
}

  1부터 7까지의 구간합 : 33

  인덱스 6의 원소를 +3만큼 수정

  4부터 7까지의 구간합 : 19

  이렇게 결과값이 출력되는 것을 확인할 수 있다.

레퍼런스

패스트캠퍼스 올인원 패키지 - 소프트웨어 베이직

구간합

  구간합이라는 것은 여러개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터 합을 구하는 것을 의미한다.

선형적으로 구간합 구하기

  인덱스 2부터 10까지의 구간합을 구한다고 하면 인덱스 2부터 10까지 계속 값을 더해가면 된다.

  이러한 방식이 선형적으로 구하는 방식이고 이 과정은 O(N)의 시간 복잡도를 갖는다.

  따라서 선형적으로 구간합을 구하는 것은 비효율적이므로 트리구조를 활용한다.

  트리구조를 활용하여 구간합을 구하는 과정은 O(logN)의 시간 복잡도를 갖는다.

구간합트리

  완전 이진트리를 이용한다. 완전이진트리는 루트부터 0, 1, 2... 순서로 내려가는데 데이터를 채워넣었다고 가정한다.

  구간합 트리의 구조는 다음과 같다.

  여기서는 루트를 1부터 시작한다고 가정했다.

  트리의 루트인 1번 인덱스는 값의 0번 인덱스부터 6번 인덱스까지의 합을 갖는다.

  트리의 2번 인덱스는 값의 0번 인덱스부터 3번 인덱스의 합

  트리의 3번 인덱스는 값의 4번 인덱스부터 6번 인덱스의 합을 가진다.

  이러한 형태로 계속 내려가게 되고 리프노드에서는 0번에서 6번까지의 값을 하나씩 갖는다.

  값을 넣어서 보면 위와 같은 형태가 된다. 자식노드의 합을 부모노드가 갖는 형태가 된다.

  그럼 최종적으로 루트노드는 모든 리프노드의 합을 값으로 갖게 된다.

  여기서 2-4의 구간합을 구한다고 하면

  루트노드는 0-6의 구간합을 모두 포함하고 있으므로 양쪽 자식노드로 내려간다.

  루트의 왼쪽자식노드에서는 0-3의 구간합을 갖고 있는데 원하는 구간은 2-4이므로 오른쪽 노드로만 내려간다.

  루트의 오른쪽자식노드에서는 4-6의 값을 갖고 있으니 왼쪽 노드로 내려간다.

  그럼 2-3의 구간합은 찾았고 4의 값을 찾기위해 6번인덱스의 노드에서 4의 값만 갖고 있는 리프노드로 내려간다.

  그럼 원하는 구간을 모두 찾은것이므로 5와 12가 채택되어 결과값을 출력하게 된다.

  이렇게 내려오는 높이는 logn이라고 할수 있기 때문에 logn만으로 구간합을 계산할 수 있게 되는 것이다.

구간합 수정하기

  만약 10번에 있는 2번 인덱스의 값을 수정한다면 그 상위노드 값을 모두 변경해줘야 한다.

예제코드

#include <stdio.h>
#define NUMBER 7

int a[] = { 7, 1 ,9, 5, 6, 4, 1 };
int tree[4 * NUMBER]; //모든 범위를 커버하기 위해 4를 곱한다.

//start : 시작인덱스, end : 끝 인덱스
int init(int start, int end, int node){
  if(start == end) return tree[node] = a[start];
  int mid = (start + end) / 2;
  
  //재귀적으로 두 부분을 나눈 뒤에 그 합을 자기 자신으로 한다.
  return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
}

//start : 시작인덱스, end : 끝 인덱스
//left, right : 구간합을 구하고자 하는 범위
int sum(int start, int end, int node, int left, int right){
  //범위 밖에 있는 경우
  if(left > end || right < start) return 0;
  
  //범위 안에 있는 경우
  if(left <= start && end <= right) return tree[node];
  
  //그렇지 않다면 두 부분으로 나누어 합을 구한다.
  int mid = (start + end) / 2;
  return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right);
}

//start : 시작인덱스, end : 끝 인덱스
//index : 구간합을 수정하고자 하는 노드
//dif : 수정할 값
void update(int start, int end, int node, int index, int dif){
  //범위 밖에 있는 경우
  if(index < start || index > end) return;
  
  //범위 안에 있으면 내려가며 다른 원소도 갱신
  tree[node] += dif;
  if(start == end) return;
  int mid = (start + end) / 2;
  update(start, mid, node * 2, index, dif); //왼쪽방향으로
  update(mid + 1, end, node * 2 + 1, index, dif); //오른쪽 방향으로
}

int main(void){
  //구간합 트리의 인덱스를 제외하고는 모두 인덱스 0부터 시작한다.
  //구간합 트리 생성하기
  //초기셋팅으로 된 7개의 원소를 전부다 초기화해서 구간합 트리를 생성
  init(0, NUMBER - 1, 1); 
  
  //구간합 구하기
  printf("0부터 6까지의 구간합 : %d\n", sum(0, NUMBER - 1, 1, 0, 6));
  
  //구간합 갱신
  printf("인덱스 5의 원소를 +3만큼 수정\n");
  update(0, NUMBER - 1, 1, 5, 3);
  
  //구간합 다시 구하기
  printf("3부터 6까지의 구간 합 : %d\n", sum(0, NUMBER - 1, 1, 3, 6));
  
  system("pause");
}

  0부터 6까지의 구간 합 : 33

  인덱스 5의 원소를 +3만큼 수정

  3부터 6까지의 구간합 : 19

  이렇게 결과값이 잘 출력되는것을 확인할 수 있다.

  3부터 6까지 구간합은 16이었지만 19로 제대로 증가한것을 확인할 수 있다.

  확인을 위해서는 첫 출력문에서 0을 3으로 바꿔보면 3부터 6까지의 구간합을 확인할 수 있다.

레퍼런스

패스트캠퍼스 올인원 패키지 - 소프트웨어 베이직

다익스트라의 최단경로 알고리즘(Dijkstra Shortest Path Algorithm)

  다익스트라의 최단경로 알고리즘은 각 간선에 대한 정보를 우선순위 큐에 담아 처리하는 방식으로

  동작원리가 프림 알고리즘(Prim Algorithm)과 흡사하다.

  다익스트라의 최단경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다.

  현실에서는 음의 간선이 존재하지 않기 때문에 다익스트라는 현실에 적합한 알고리즘이다.

과정

  그래프의 시작점을 선택하여 트리 T에 포함시킨다.

  T에 포함된 노드와 T에 포함되지 않은 노드 사이의 간선중에서 이동거리가 가장 작은 간선을 찾는다.

  해당 간선에 연결된 T에 포함되지 않은 노드를 트리 T에 포함시킨다.

  모든 노드가 포함될때까지 반복한다.

  이와 같은 그래프가 있고 1에서 시작한다고 하면

  자기자신은 0, 인접노드는 해당 간선값, 인접하지 않은 노드는 무한이다.

  그럼 자기자신을 제외한 노드중에서 가장 거리가 짧은 노드를 먼저 방문하기 때문에 4를 방문하게 된다.

  4에서는 인접노드로 3과 5가 있다.

  3의 경우는 1에서 4를 거쳐 3으로 이동하면 1 + 3의 비용이 소모된다.

  원래의 비용인 5보다 더 작기 때문에 3의 거리비용을 4로 변경해준다.

  5는 무한이었으니 4를 거쳐 이동하는 비용인 2로 변경해준다.

  그럼 이제 2와 5가 같은 최소값을 갖고 있는데 둘중 어디를 먼저가도 상관없다.

  5를 먼저 갔다고 했을 때 5에서는 3과 6이 인접노드이다.

  3의 경우는 원래 거리비용이 4였지만 1->4->5 를 통해 이동하면 3의 비용만이 소모되므로

  3으로 변경해준다.

  6은 무한이었기 때문에 5까지의 거리비용인 2에 6으로 이동하는 거리비용인 2를 더해 4의 거리비용으로

  변경해준다.

  그럼 이제 방문하지 않은 노드중 최소비용을 갖고 있는 2로 이동한다.

  2에서는 인접노드가 4밖에 존재하지 않는다.

  현재 2의 거리비용은 2이고 4로 이동하는 거리비용은 2이므로 총 4를 갖게 되는데 현재 4는 1의 거리비용을

  갖고 있기 때문에 변경하지 않고 그대로 둔다.

  남은 노드인 3, 6중에 3의 거리비용이 더 작으므로 3으로 이동한다.

  3에서는 2와 6이 인접해있고 2로 이동하는 비용을 더하면 6, 6으로 이동하는것은 8의 비용이 소모되는데

  기존 2와 6이 갖고 있는 거리비용이 더 작기 때문에 변경하지 않고 6으로 이동한다.

  그럼 마지막으로 6으로 이동하게 되고 0, 2, 3, 1, 2, 4가 각 노드의 최소 거리비용이 된다.

  다익스트라 알고리즘은 각 간선에 대한 정보를 우선순위큐에 담아 처리하는 방식으로 구현할 수 있으며

  O(ElogV)의 시간 복잡도를 갖는다.

예제코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define NODE_MAX 20001
#define EDGE_MAX 600001 //양방향 간선이므로 300,000개

typedef struct{ //각 간선의 정보
  int cost;
  int node;
} Edge;

void swap(Edge* a, Edge* b){ //두개의 간선에 대한 정보를 교체
  Edge temp;
  temp.cost = a->cost;
  temp.node = a->node;
  a->cost = b->cost;
  a->node = b->node;
  b->cost = temp.cost;
  b->node = temp.node;
}

typedef struct{
  Edge* heap[EDGE_MAX];
  int count;
} priorityQueue;

void enQueue(priorityQueue* pq, Edge* edge){
  if(pq->count >= EDGE_MAX) return;
  pq->heap[pq->count] = edge;
  int now = pq->count;
  int parent = (pq->count - 1) / 2;
  
  //새 원소를 삽입한 이후에 상향식으로 힙을 구성
  while(now > 0 && pq->heap[now]->cost < pq->heap[parent]->cost){
    swap(pq->heap[now], pq->heap[parent]);
    now = parent;
    parent = (parent - 1) / 2;
  }
  pq->count++;
}

Edge* deQueue(priorityQueue* pq){
  if(pq->count <= 0) return NULL;
  Edge* res = pq->heap[0];
  pq->count--;
  pq->heap[0] = pq->heap[pq->count];
  int now = 0, leftChild = 1, rightChild = 2;
  int target = now;
  
  //새원소를 추출한 이후에 하향식으로 힙을 구성
  while(leftChild < pq->count){
    if(pq->heap[target]->cost > pq->heap[leftChild]->cost) target = leftChild;
    if(pq->heap[target]->cost > pq->heap[rightChild]->cost && rightChild < pq->count) target = rightChild;
    if(target == now) break; //더이상 내려가지 않아도 될 때 종료
    else{
      swap(pq->heap[now], pq->heap[target]);
      now = target;
      leftChild = now * 2 + 1;
      rightChild = now * 2 + 2;
    }
  }
  return res;
}

typedef struct Node{
  Edge* data;
  struct Node* next;
} Node;

Node** adj;
int ans[NODE_MAX]; //특정노드까지의 최단거리값

void addNode(Node** target, int index, Edge* edge){
  if(target[index] == NULL){
    target[index] = (Node*)malloc(sizeof(Node));
    target[index]->data = edge;
    target[index]->next = NULL;
  }
  else {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = edge;
    node->next = target[index];
    target[index] = node;
  }
}

int main(void){
  int n, m, k;
  scanf("%d %d %d", &n, &m, &k);
  adj = (Node**)malloc(sizeof(Node*) * (n + 1)); //노드의 개수만큼 연결리스트 생성
  
  for(int i = 1; i <= n; i++){ //연결리스트 초기화
    adj[i] = NULL;
    ans[i] = INT_MAX; //모든 노드로 갈수있는 비용은 전부 무한이라고 초기화
  }
  priorityQueue* pq;
  pq = (priorityQueue*)malloc(sizeof(priorityQueue));
  pq->count = 0;
  
  for(int i = 0; i < m; i++){ //방향그래프 형식
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c); //a에서 b까지 가는 거리가 C이다
    Edge* edge = (Edge*)mallco(sizeof(Edge));
    edge->node = b;
    edge->cost = c;
    addNode(adj, a, edge); //연결리스트에 추가해서 a번째 인덱스에 원소 b를 추가하는 형태
  }
  //간선에 대한 정보들이 우선순위 큐에 들어간것
  
  
  //다익스트라 알고리즘 시작
  ans[k] = 0; //출발하고자하는 노드의 비용 설정 시작노드는 비용이 0
  Edge* start = (Edge*)malloc(sizeof(Edge));
  start->cost = 0; start->node = k; enQueue(pq, start);//출발노드에 대한 간선정보를 큐에 넣는다
  while(1){ //모든 간선에 대한 정보를 큐에 담았다가 꺼내면서 처리
    Edge* now = deQueue(pq); //큐에 담겨있는 원소 추출
    if(now == NULL) break;
    int curNode = now->node;
    int curCost = now->cost;
    if(ans[curNode] < curCost) continue;
    //최단경로이기 때문에 현재 보고있는 비용이 테이블에 담은 비용보다 크다면 무시하고 넘어간다
    
    Node* cur = adj[curNode]; //그렇지 않다면 새롭게 특정한 노드가 추가되었다는 것이므로
    while(cur != NULL){ //그 노드에 연결되어있는 모든 노드를 확인한다
      Edge* temp = cur->data;
      temp->cost += curCost; //확인했을 때 해당노드로 건너가는 비용을 cost에 담는다
      
      if(temp->cost < ans[temp->node]){
        //현재 테이블에 담겨있던 해당 노드에 대한 최단거리 비용이
        //현재 보고있는 비용보다 크다면 더 작은값으로 갱신
        ans[temp->node] = temp->cost;
        enQueue(pq, temp);
        //테이블 갱신
        //이후에 다시 해당 간선을 우선순위 큐에 담아서 다시한번
        //간선데이터를 확인하도록 한다.
      }
      cur = cur->next;
    }
    //내부 while End
    //모든 간선을 확인해서 더 적은비용으로 갱신하겠다는 것.
    //이것이 다익스트라 알고리즘의 핵심이다.
  }
  
  for(int i = 1; i <= n; i++){
    if(ans[i] == INT_MAX) printf("INF\n");
    //무한이라는 값을 갖고 있으면 해당 노드로는 도착할 수 없기 때문에 INF출력
    else printf("%d\n", ans[i]);
  }
  system("pause");
}

  3 3 1

  1 2 10

  1 3 30

  2 3 5

  이렇게 입력하면

  0

  10

  15

  이렇게 출력된다.

  입력된 값을 보면

  노드수  간선수  출발노드

  1에서 2까지 비용 10

  1에서 3까지 비용 30

  2에서 3까지 비용 5

  이렇게 입력된것이고

  그럼 1의 비용은 시작점이니까   0

  2는 10의 비용을 갖고 있으니    10

  3은 1에서 3으로 가는 비용(30)과

  1에서 2를 거쳐 가는 비용(15)

  두가지가 있으니 더 작은값인    15

  이렇게 처리된다.

레퍼런스

● 패스트캠퍼스 올인원 패키지 - 소프트웨어 베이직

● m.blog.naver.com/ndb796/221234424646

Kruskal 알고리즘이란

  탐욕적인 방법(greedy method)을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소비용으로

  연결하는 최적 해답을 구하는 것

    greedy method

      결정을 해야할때마다 그 순간에 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 것.

      greedy method는 그 순간에는 최적이지만 전체적인 관점에서 최적이라는 보장이 없기 때문에 반드시 

      검증해야 한다.

      다행히 Kruskal 알고맂므은 최적의 해답을 주는것으로 증명되어 있다.

    MST(최소비용 신장트리)가 최소비용의 간선으로 구성되되고 사이클을 포함하지 않는다는 조건에 근거하여

    각 다께에서 사이클을 이루지 않는 최소비용간선을 선택한다.

Kruskal 알고리즘의 동작

  그래프의 간선들을 가중치의 오름차순으로 정렬한다.

  정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.

    즉, 가장 낮은 가중치를 먼저 선택한다.

    사이클을 형성하는 간선을 제외한다.

  해당 간선을 현재의 MST의 집합에 추가한다.

Kruskal 알고리즘의 구체적인 동작과정

  Kruskal 알고리즘을 이용하여 MST를 만드는 과정

    간선 선택을 기반으로 하는 알고리즘

    이전 단계에서 만들어진 신장트리와는 상관없이 무조건 최소 간선만을 선택하는 방법

주의사항

  다음 간선을 이미 선택된 간선들의 집합에 추가할 때 사이클을 생성하는지를 체크해야 한다.

    새로운 간선이 이미 다른 경로에 의해 연결되어 있는 정점들을 연결할 때 사이클이 형성된다.

    즉, 추가할 새로운 간선의 양끝 정점이 같은 집합에 속해 있으면 사이클이 형성된다.

  싸이클 생성여부를 확인하는 방법

    추가하고자 하는 간선의 양끝 정점이 같은 집합에 속해 있는지를 먼저 검사해야 한다.

    union-find 알고리즘 사용

Kruskal 알고리즘의 시간 복잡도

  union-find 알고리즘을 이용하면 Kruskal 알고리즘의 시간 복잡도는 간선들을 정렬하는 시간에 좌우된다.

  즉, 간선 e개를 퀵 정렬과 같은 효율적인 알고리즘으로 정렬한다면

    Kruskal알고리즘의 시간 복잡도는 O(elog₂e)이 된다.

  Prim 알고리즘의 시간 복잡도는 O(n^2)이므로

    그래프 내에 적은 숫자의 간선만을 가지는 희소그래프(Sparse Graph)의 경우 Kruskal 알고리즘이 적합하고

    그래프에 간선이 많이 존재하는 밀집그래프(Dense Graph)의 경우는 Prim 알고리즘이 적합하다.

예제코드

import java.util.*;

public class Kruskal {
  static int V, E;
  static PriorityQueue<Edge> pq;
  static ArrayList<Edge> MST;
  static int parent[];

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
      
    V = sc.nextInt();
    E = sc.nextInt();
        
    pq = new PriorityQueue<>();
    MST = new ArrayList<>();
    parent = new int[V + 1];
        
    //for init
    for(int i = 0; i <= V; i++){
      parent[i] = i;
    }
        
    for(int i = 1; i <= E; i++){
      int u = sc.nextInt();
      int v = sc.nextInt();
      int val = sc.nextInt();
            
      pq.add(new Edge(u, v, val));
    }
        
    while(MST.size() < (V - 1)){
      Edge e = pq.poll();
          
      if(find(e.begin) != find(e.end)){
        MST.add(e);
        union(e.begin, e.end);
      }
    }
        
    for(int i = 0; i < MST.size(); i++){
      System.out.println(MST.get(i).begin + " " + MST.get(i).end + " " + MST.get(i).val);
    }
  }
    
  public static int find(int n){
    if(n == parent[n]){
      return n;
    }else{
      int p = find(parent[n]);
      parent[n] = p;
      return p;
    }
  }
    
  public static void union(int n1, int n2){
    int p1 = find(n1);
    int p2 = find(n2);
        
    if(p1 != p2){
      parent[p1] = p2;
    }
  }
    
  public static class Edge implements Comparable<Edge>{
        
    int begin, end, val;
        
    public Edge(int b, int e, int v){
      this.begin = b;
      this.end = e;
      this.val = v;
    }
        
    @Override
    public int compareTo(Edge o){
      return this.val - o.val;
    }
  }
}

레퍼런스

● gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html

● ukyonge.tistory.com/11

프림(Prim)알고리즘이란

  시작 정점에서 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법

프림 알고리즘의 동작

  1. 시작 단계에서는 시작 정점만이 MST(최소 비용 신장 트리) 집합에 포함된다.

  2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다.

     즉, 가장 낮은 가중치를 먼저 선택한다.

  3. 위의 과정을 트리가 (n - 1)개의 간선을 가질때까지 반복한다.

프림 알고리즘의 구체적인 동작과정

  프림 알고리즘을 이용하여 MST를 만드는 과정

    정점 선택을 기반으로 하는 알고리즘

    이전 단계에서 만들어진 신장트리를 확장하는 방법

프림 알고리즘의 시간 복잡도

  주 반복문이 정점의 수 n만큼 반복하고, 내부 반복문이 n번 반복

    프림 알고리즘의 시간 복잡도는 O(N^2)이 된다.

  Kruskal 알고리즘의 시간 복잡도는  O(elog₂e) 이므로

    그래프 내에 적은 숫자의 간선만을 갖는 '희소그래프(Sparse Graph)'의 경우 Kruskal 알고리즘이 적합하고

    그래프에 간선이 많이 존재하는 '밀집그래프(Dense Graph)'의 경우는 prim 알고리즘이 적합하다.

예제코드

  강의 C언어 예제코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define NODE_MAX 1001 //노드가 최대 1000개
#define EDGE_MAX 200001 //양방향 간선이므로 100,000개

/*
  3 3
  1 2 8
  1 3 9
  2 3 10
  을 입력하면 17이 출력된다.
  
  1, 2, 3을 전부 연결할때는 두개간선만 연결하면 되기 때문에
  8 + 9가 되어 17이 출력되는것을 확인할 수 있다.
*/

typedef struct {
  int cost;
  int node;
} Edge; //각 간선의 정보

void swap(Edge* a, Edge* b){ //두개의 간선에 대한 정보를 교체
  Edge temp;
  temp.cost = a->cost;
  temp.node = a->node;
  a->cost = b->cost;
  a->node = b->node;
  b->cost = temp.cost;
  b->node = temp.node;
}

typedef struct{
  Edge* heap[EDGE_MAX];
  int count;
} priorityQueue;

void enQueue(priorityQueue* pq, Edge* edge){
  if(pq->count >= EDGE_MAX) return; //총 들어갈 수 있는 간선의 크기를 벗어난 경우
  pq->heap[pq->count] = edge; //마지막 인덱스에 새 원소 삽입
  int now = pq->count;
  int parent = (pq->count - 1) / 2;
  //새 원소를 삽입한 이후에 상향식으로 힙을 구성
  while(now > 0 && pq->heap[now]->cost < pq->heap[parent]->cost){
    swap(pq->heap[now], pq->heap[parent]);
    now = parent;
    parent = (parent - 1) / 2;
  }
  pq->count++;
}

Edge* deQueue(priorityQueue* pq){
  if(pq->count <= 0) return NULL;
  Edge* res = pq->heap[0];
  pq->count--;
  pq->heap[0] = pq->heap[pq->count];
  int now = 0, leftChild = 1, rightChild = 2;
  int target = now;
  //새원소를 추출한 이후에 하향식으로 힙을 구성
  while(leftChild < pq->count){
    if(pq->heap[target]->cost > pq->heap[leftChild]->cost) target = leftChild;
    if(pq->heap[target]->cost > pq->heap[rightChild]->cost && rightChild < pq->count) target = rightChild;
    if(target == now) break;
    else{
      swap(pq->heap[now], pq->heap[target]);
      now = target;
      leftChild = now * 2 + 1;
      rightChild = now * 2 + 2;
    }
  }
  return res;
}

typedef struct Node{
  Edge* data;
  struct Node* next;
} Node;

Node** adj;
int d[NODE_MAX];

void addNode(Node** target, int index, Edge* edge){
  if(target[index] == NULL){
    target[index] = (Node*)malloc(sizeof(Node));
    target[index]->data = edge;
    target[index]->next = NULL;
  }
  else{
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = edge;
    node->next = target[index];
    target[index] = node;
  }
}

int main(void){
  int n, m;
  scanf("%d %d", &n, &m); //정점과 간선의 개수 입력
  adj = (Node**)malloc(sizeof(Node*) * (n + 1)); //정점의 개수만큼 동적할당으로 연결리스트 생성
  for(int i = 1; i <= n; i++){
    adj[i] = NULL; //모든 연결리스트는 NULL로 초기화
  }
  priorityQueue* pq;
  pq = (priorityQueue*)malloc(sizeof(priorityQueue)); //우선순위 큐 생성
  pq->count = 0;
  for(int i = 0; i < m; i++){ //모든 간선에 대한 정보 입력
    int a, b, c; //c는 가중치. a에서 b까지 가는데 c만큼 소요되는것.
    scanf("%d %d %d", &a, &b, &c);
    Edge* edge1 = (Edge*)malloc(sizeof(Edge));
    edge1->node = b;
    edge1->cost = c;
    addNode(adj, a, edge1);
    Edge* edge2 = (Edge*)malloc(sizeof(Edge));
    edge2->node = a;
    edge2->cost = c;
    addNode(adj, b, edge2);//무방향 그래프
  }
  
  //프림 알고리즘 시작
  long long res = 0;
  Edge* start = (Edge*)malloc(sizeof(Edge)); //시작점
  start->cost = 0;
  start->node = 1;
  enQueue(pq, start);
  
  for(int i = 1; i <= n; i++){
    //신장트리의 경우 총 n개의 정점이 최정적으로 만들어진 신장트리에
    //포함되기 때문에 n번만큼 반복
    int nextNode = -1, nextCost = INT_MAX;
    while(1){
      Edge* now = deQueue(pq);
      if(now == NULL) break;
      nextNode = now->node;
      if(!d[nextNode]){
        nextCost = now->cost; break;
        //방문하지 않은 노드들 중에서 가장 비용이 적은 노드를
        //우선순위 큐에서 꺼내준다.
        //우선순위큐에는 비용이 적은 노드 순으로 들어가있기 때문에
        //과정자체가 방문하지 않은 하나의 노드를 찾겠다는 것.
      }
    }
    if(nextCost == INT_MAX) printf("연결 그래프가 아닙니다.\n");
    //못찾았다면 연결그래프가 아닌것이기 때문에 오류메세지를 띄운다.
    res += nextCost; //가중치를 누적.
    d[nextNode] - 1; //방문처리
    Node* cur = adj[nextNode];
    while(cur != NULL){
      enQueue(pq, cur->data);
      cur = cur->next; //인접한 모든 노드를 확인하기 위한 반복문
    }
  }
  printf("%lld\n", res);
  system("pause");
}

  자바 예제코드

import java.util.*;

public class prim {
  static int V, E;
  static boolean visit[];
  static ArrayList<Edge>[] graph;
  static ArrayList<Edge> MST;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    V = sc.nextInt(); // 정점
    E = sc.nextInt(); // 간선

    graph = new ArrayList[V + 1]; //정점의 연결을 저장할 리스트
    visit = new boolean[V + 1];  //방문체크

    for(int i = 0; i <= V; i++){
      graph[i] = new ArrayList<>(); // 정점의 수 + 1로 초기화

    }

    MST = new ArrayList<>();

    for(int i = 1; i <= E; i++){
      int u = sc.nextInt();
      int v = sc.nextInt();
      int val = sc.nextInt();

      graph[u].add(new Edge(u, v, val));
      graph[v].add(new Edge(u, v, val));
    }

    int point = 1; //시작포인트
    solve(point);
    
    for(int i = 0; i < MST.size(); i++){
      System.out.println(MST.get(i).begin + " " + MST.get(i).end + " " + MST.get(i).value);
      //출력.
      //begin = 시작, end = 도착, value = 간선
    }
  }

  private static void solve(int P){

    PriorityQueue<Edge> pq = new PriorityQueue<>();
    Queue<Integer> queue = new LinkedList<>();

    queue.add(P); //큐에 시작 정점 add
    while(!queue.isEmpty()){ //큐가 비어있지 않다면
      int now = queue.poll();
      visit[now] = true;//큐 순서에 따라 해당하는 인덱스 방문처리

      for(Edge e : graph[now]){
        if(!visit[e.end]) {//방문하지 않았다면 pq에 add
          pq.add(e);
        }
      }

      while(!pq.isEmpty()){//pq가 비어있을때까지 반복
        Edge e = pq.poll();
        if(!visit[e.end]){//방문하지 않았다면 queue에 넣어주고 방문처리 한 뒤 MST에 add
          queue.add(e.end);
          visit[e.end] = true;
          MST.add(e);
          break;
        }
      }
  }


  }

  public static class Edge implements Comparable<Edge>{
    int begin;
    int end;
    int value;

    public Edge(int b, int e, int v){
      this.begin = b;
      this.end = e;
      this.value = v;
    }

    @Override
    public int compareTo(Edge o){
      return this.value - o.value;
    }
  }
}

레퍼런스

● 패스트캠퍼스 올인원 패키지 - 소프트웨어 베이직

● gmlwjd9405.github.io/2018/08/30/algorithm-prim-mst.html

● ukyonge.tistory.com/12

신장트리(Spanning Tree)

  신장트리란 특정한 그래프에서 모든 정점을 포함하는 그래프이다.

  스패닝트리라고도 하며 그래프의 최소 연결 부분 그래프이다.

  최소연결이라는 것은 간선의 수가 가장 적다는 것을 의미한다.

  n개의 정점을 가지는 그래프의 최소 간선의 수는 (n - 1)개 이고, (n - 1)개의 간선으로 연결되어 있으면 필연적으로

  트리형태가 되는데 이것이 바로 Spanning Tree가 된다.

  즉, 그래프에서 일부 간선을 선택해서 만든 트리이다.

Spanning Tree의 특징

  DFS, BFS를 이용하여 탐색 도중에 사용된 간선만 모으면 그래프에서 신장트리를 찾을 수 있다.

  하나의 그래프에는 많은 신장트리가 존재할 수 있다.

  Spanning Tree는 트리의 특수한 형태이므로 모든 정점들이 연결되어있어야 하고 사이클을 포함해서는 안된다.

  따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n - 1)개의 간선으로 연결한다.

Spanning Tree의 사용사례

  통신네트워크 구축.

  예를 들어 회사내의 모든 전화기를 가장 적은 수의 케이블을 사용하여 연결하고자 하는 경우

  n개의 위치를 연결하는 통신 네트워크를 최소의 링크(간선)를 이용하여 구축하고자 하는 경우에

  최소 링크의 수는 (n - 1)개가 되고 따라서 Spanning Tree 가 가능해진다.

최소신장트리(Minimum Spanning Tree, MST)

  최소신장트리(Minimum Spanning Tree)란 스패닝 트리 중에서 간선의 가중치 합이 가장 작은 트리를 의미한다.

  각 간선의 가중치가 동일하지 않을 때 단순히 가장 적은 간선을 사용한다고 해서 최소비용이 얻어지는것은 아니다.

  MST는 간선에 가중치를 고려하여 최소비용의 Spanning Tree를 선택하는 것을 말한다.

  즉, 네트워크(가중치를 간선에 할당한 그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것이다.

MST의 특징

  간선의 가중치 합이 최소여야 한다.

  n개의 정점을 갖는 그래프에 대해 반드시 (n - 1)개의 간선만을 사용해야 한다.

  사이클이 포함되어서는 안된다.

MST사용사례

  통신망, 도로망, 유통망에서 길이, 구축비용, 전송시간 등을 최소로 구축하려는 경우

  도로건설 : 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제

  전기회로 : 단자들을 모두 연결하면서 전선의 길이가 가장 최소가 되도록 하는 문제

  통신 : 전화선의 길이가 최소가 되도록 전화케이블 망을 구성하는 문제

  배관 : 파이프를 모두 연결하면서 파이프의 총 길이가 최소가 되도록 연결하는 문제

MST구현방법

  1. Kruskal MST 알고리즘

    탐욕적인 방법(greedy method)을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을

    최소비용으로 연결하는 최적 해답을 구하는 것.

    MST가 최소비용의 간선으로 구성되고 사이클을 포함하지 않는다는 조건에 근거하여 각 단계에서 사이클을

    이루지 않는 최소비용간선을 선택한다.

    간선 선택을 기반으로 하는 알고리즘이다.

    이전단계에서 만들어진 신장트리와는 무조건 최소 간선만을 선택하는 방법이다.

  과정

    그래프의 간선들을 가중치의 오름차순으로 정렬한다.

    정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.

    즉, 가장 낮은 가중치를 먼저 선택한다.

    사이클을 형성하는 간선을 제외한다.

    해당 간선을 현재의 MST의 집합에 추가한다.

  크루스칼 알고리즘 예제코드

    myyoun.tistory.com/109

  2. prim MST 알고리즘

    시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법

    정점 선택을 기반으로 하는 알고리즘이다.

    이전단계에서 만들어진 신장트리를 확장하는 방법이다.

  과정

    시작단계에서는 시작 정점만이 MST집합에 포함된다.

    앞 단계에서 만들어진 MST집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다.

    즉, 가장 낮은 가중치를 먼저 선택한다.

    우위 과정을 트리가 (n - 1)개의 간선을 가질때까지 반복한다.

  프림 알고리즘 예제코드

    myyoun.tistory.com/108

레퍼런스

gmlwjd9405.github.io/2018/08/28/algorithm-mst.html