공부하는블로그

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

해시(Hash)

  해시는 데이터를 최대한 빠른 속도로 관리할 수 있도록 도와주는 자료구조이다.

  해시를 사용하면 메모리공간이 많이 소모되지만 매우 빠른 속도로 데이터를 처리할 수 있다.

  빠르게 데이터에 접근할 수 있다는 점에서 데이터베이스 등의 소프트웨어에서 활용된다.

동작과정

  입력데이터를

  78/AA

  12/BB

  55/CC

  64/DD

  라고 입력하고 해시함수를 (n mod 10)으로 입력값 n을 10으로 나눈 나머지값을 키(key)로 갖게 한다면

  인덱스 8의 값으로 AA가 들어가고 2에는 BB, 5에는 CC, 4에는 DD가 값(value)로 들어가게 된다.

  이런식으로 해시함수를 이용하게 되면 기존의 값들이 특정한 값으로 매칭이 되어서 차곡차곡 쌓이게 되는

  형태다.

  특정한 값(value)을 찾을때는 키(key)로 접근할 수 있는데 배열에서의 index를 의미하는것과 같다.

  일반적으로 해시함수는 모듈로(modulo)연산등의 수학적 연산으로 이루어져 있으므로 O(1)만에

  값에 접근할 수 있다.

해싱(Hashing)

  해싱 알고리즘은 나눗셈법(Division Method)이 가장 많이 활용된다. 입력값을 테이블의 크기로 나눈 나머지를

  키로 이용하는 방식이다. 테이블의 크기는 소수(Prime Number)로 설정하는 것이 효율성이 높다.

해시의 충돌(Collision)

  해시함수의 입력값으로는 어떠한 값이나 모두 들어갈 수 있지만, 해시함수를 거쳐 생성되는 키의 경우의수는

  한정적이기 때문에 키 중복이 발생할 수 있다.

  해시테이블에서 키가 중복되는 경우를 충돌(Collision)이라고 표현한다.

  입력데이터가 77/AA, 17/BB라고 하고 해시함수를 (n mod 10)이라고 했을 때 두 데이터 모두 7이라는

  키값을 갖게 된다. 이러한 문제가 발생하는 것이 충돌이다.

  아무리 잘 만들어진 해시함수라도 충돌이 발생할 수 밖에 없다. 충돌을 처리하는 방법은 다음과 같이

  두가지유형으로 분류할 수 있다.

  1. 충돌을 발생시키는 항목을 해시테이블의 다른 위치에 저장 : 선형조사법, 이차조사법 등

  2. 해시테이블의 하나의 버킷(Bucket)에 여러개의 항목을 저장 : 체이닝(Chaning) 등

선형조사법

  입력데이터가 1/AA, 5/BB, 10012/CC, 20019/DD일 때 해시함수로 (n mod 10007)처리한다고 하면

  1과 5는 일단 값이 들어간다. 10012를 10007로 나눈 나머지값은 5가 되는데 이미 5라는 키값은 존재한다.

  그럼 중복이 되기때문에 다음 인덱스로 들어간다. 그럼 1에는 AA, 5에는 BB, 6에는 CC가 들어가게 된다.

  마지막 데이터인 20019역시 나머지값이 5이므로 CC가 들어갈때와 동일하게 중복이 된다.

  그럼 5에서 중복이기때문에 6으로 가지만 6역시 키값이 존재하므로 7에 값이 들어간다.

  이렇게 차례로 하나씩 탐색하는것 즉, 선형적으로 탐색한다고 해서 선형조사법이라고 한다.

선형조사법 예제코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h> //time을 사용하는 이유는 무작위 데이터를 5000개 삽입할 것이기 때문
#define TABLE_SIZE 10007 //테이블의 크기는 소수로 설정하는것이 좋다.
#define INPUT_SIZE 5000

typedef struct{
  int id;
  char name[20];
} Student;

//해시테이블 초기화
void init(Student** hashTable){
  for(int i = 0; i < TABLE_SIZE; i++){
    hashTable[i] = NULL;
    //각 테이블의 포인터값을 NULL로 설정
    //학생정보가 비어있다고 초기화를 하는것
  }
}

//해시테이블의 메모리를 반환
void destructor(Student** hashTable){
  for(int i = 0; i < TABLE_SIZE; i++){
    if(hashTable[i] != NULL){
      free(hashTable[i]);
      //특정한 학생이 해당테이블에 존재한다면
      //그것을 다 할당해제
    }
  }
}

//해시테이블 내 빈 공간을 선형탐색으로 찾는다.
int findEmpty(Student** hashTable, int id){
  int i = id % TABLE_SIZE;
  
  while(1){
    if(hashTable[i % TABLE_SIZE] == NULL){
      //비어있다면 인덱스를 반환
      return i % TABLE_SIZE;
    }
    i++;
  }
}

//특정한 ID값에 매칭되는 데이터를 해시테이블 내에서 찾는다.
int search(Student** hashTable, int id){
  int i = id % TABLE_SIZE;
  
  while(1){
    if(hashTable[i % TABLE_SIZE] == NULL) return -1;
    //해당 인덱스가 비어있다면 -1을 리턴
    else if(hashTable[i % TABLE_SIZE]->id == id) return i;
    //해당 인덱스의 id가 id와 같다면 i인 해당 인덱스를 리턴
    i++;
  }
}

//특정한 키 인덱스에 데이터를 삽입
void add(Student** hashTable, student* input, int key){
  hashTable[key] = input;
}

//해시 테이블에서 특정한 키의 데이터를 반환
Student* getValue(Student** hashTable, int key){
  return hashTable[key];
}

//해시테이블에 존재하는 모든 데이터를 출력
void show(Student** hashTable){
  for(int i = 0; i < TABLE_SIZE; i++){
    if(hashTable[i] != NULL){ //해당 버킷이 비어있지 않다면 출력
      printf("키 : [%d] 이름 : [%s]\n", i, hashTable[i->name);
    }
  }
}

int main(void){
  Student** hashTable;
  hashTable = (Student**)malloc(sizeof(Student) * TABLE_SIZE);
  //테이블 사이즈만큼 학생데이터가 들어갈 수 있는 테이블을 만든다.
  init(hashTable);
  //해당 테이블을 초기화
  
  for(int i = 0; i < INPUT_SIZE; i++){
    Student* student = (Student*)malloc(sizeof(Student));
    student->id = rand() % 1000000;
    //랜덤으로 만들어진 숫자를 1000000으로 나눈 나머지값
    //10007을 넘기지 않기 위함이다.
    sprintf(student->name, "사람%d", student->id);
    //학생의 이름은 사람+학생번호로 만들어준다.
    
    if(search(hashTable, student->id) == -1){
      //중복되는 ID는 존재하지 않도록
      //해당 학생 번호에 해당하는 key값을 테이블에서 매칭하도록 찾아야 한다.
      int index = findEmpty(hashTable, student->id);
      add(hashTable, student, index);
    }
  }
  
  show(hashTable);
  destructor(hashTable);
  system("pause");
  return 0;
}

  실행해보면 많은 데이터가 삽입되었지만 중복된 키값은 없다는 것을 확인할 수 있다.

  그리고 설정한것처럼 10007이 넘는 키값은 존재하지 않는다.

선형조사법의 단점

  선형조사법은 충돌이 발생하기 시작하면 유사한 값을 갖는 데이터끼리 서로 밀집되는 집중결합문제가 존재한다.

  예를들어 데이터 5라는 키에 들어가야되는 값이 3개 존재했다면 5, 6, 7에 순차적으로 들어가 밀집되는 문제다.

  선형조사법이라고 해도 해시테이블의 크기가 비약적으로 크다면, 다시말해 메모리를 많이 소모한다면 충돌이 적게

  발생하므로 매우 빠른 데이터 접근속도를 가질 수 있다.

  하지만 일반적인 경우, 해시테이블의 크기는 한정적이므로 충돌이 최대한 적게 발생하도록 해야한다.

이차조사법

  선형조사법의 단점을 보완하기 위한 조사법이다.

  선형조사법을 약간 변형한 형태로 키값을 선택할 때 완전제곱수를 더해 나가는 방식이다.

  아까와 같은 1, 5, 10012, 20019라는 데이터와 (n mod 10007)이라는 해시 함수를 사용한다면

  10012부터 충돌이 되는데 처음 중복시에는 다음 인덱스만 체크해서 넣어준다.

  그 다음 20019에서 또 충돌이 발생했을 때는 2의 제곱인 4만큼의 공간을 넘어가서 입력하는 방식이다.

조사법 테이블 크기 재설정

  일반적으로 선형조사법, 이차조사법 등의 조사법에서 테이블이 가득차게 되면 테이블의 크기를 확장하여 계속해서

  해시테이블을 유지할 수 있도록 한다.

체이닝(Chaning)

  체이닝 기법은 연결리스트를 활용해 특정한 키를 갖는 항목들을 연결하여 젖앟나다.

  연결리스트를 사용한다는 점에서 삽입과 삭제가 용이하다. 또한 테이블 크기 재설정 문제는 '동적할당'을 통해서

  손쉽게 해결할 수 잇다. 다만 동적할당을 위한 추가적인 메모리공간이 소모된다는 단점이 있다.

  연결리스트를 사용한다는 것은 5/BB, 10012/CC, 20019/DD의 데이터가 (n mod 10007)의 해시함수를 통했을 때

  키값이 5로 중복되는데 이것을 5라는 하나의 키에 BB, CC, DD 형태의 연결리스트로 만들어 해결하는 것이다.

체이닝 예제코드

#define _CRT_SECURE_NO_WARINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define TABLE_SIZE 10007
#define INPUT_SIZE 5000

typedef struct{
  int id;
  char name[20];
} Student;

//학생구조체가 연결리스트 형태로 들어갈 수 있도록 각각의 bucket을 설정
//즉, 하나의 키에 해당하는 데이터가 여러개 들어갈 수 있다는 것
typedef struct{
  Student* data;
  struct Bucket* next;
} Bucket;

//해시테이블 초기화
void init(Bucket** hashTable){
  for(int i = 0; i < TABLE_SIZE; i++){
    hashTable[i] = NULL;
  }
}

//해시 테이블의 메모리를 반환
void destructor(Bucket** hashTable){
  for(int i = 0; i < TABLE_SIZE; i++){
    if(hashTable[i] != NULL){
      free(hashTable[i]);
    }
  }
}

//체이닝 데이터 탐색함수
int isExist(Bucket** hashTable, int id){
  int i = id % TABLE_SIZE;
  
  if(hashTable[i] == NULL) return 0; //해당 테이블이 NULL이라면
  else{ //해당키에 해당하는 연결리스트를 하나씩 확인
    Bucket* cur = hashTable[i];
    
    while(cur != NULL){
      if(cur->data->id == id) return 1;
      cur = cur->next;
      //값이 존재하지 않을때까지 반복
    }
  }
  return 0;
}

//체이닝 데이터 삽입 함수. 특정한 키 인덱스에 데이터를 삽입
void add(Bucket** hashTable, Student* input){
  int i = input->id % TABLE_SIZE;
  
  if(hashTable[i] == NULL){ 
    //해당키에 해당하는 연결리스트가 비어있다면 바로 첫번째 원소를 넣는다
    hashTable[i] = (Bucket*)malloc(sizeof(Bucket);
    hashTable[i]->data = input;
    hashTable[i]->next = NULL;
  }
  else{
    //그렇지 않다면 해당 연결리스트의 앞부분에 새로운 노드가 들어간다.
    Bucket* cur = (Bucket*)malloc(sizeof(Bucket));
    cur->data = input;
    cur->next = hashTable[i];
    hashTable[i] = cur;
  }
}

//해시테이블에 존재하는 모든 데이터를 출력
void show(Bucket** hashTable){
  for(int i = 0; i < TABLE_SIZE; i++){ //테이블에 들어가있는 모든 원소 확인
    if(hashTable[i] != NULL){
      Bucket* cur = hashTable[i];//해당 버킷에 들어가있는 데이터를 다 출력
      
      while(cur != NULL){
        printf("키 : [%d] 이름 : [%s]\n", i, cur->data->name);
        cur = cur->next;
      }
    }
  }
}

int main(void){
  Bucket** hashTable;
  hashTable = (Bucket**)malloc(sizeof(Bucket) * TABLE_SIZE);
  init(hashTable);
  
  for(int i = 0; i < INPUT_SIZE; i++){
    Student* student = (Student*)malloc(sizeof(Student));
    student->id = rand() * 1000000;
    sprintf(student->name, "사람%d", student->id);
    
    if(!isExist(hashTable, student->id)) {//중복체크
      add(hashTable, student);
      //중복이 되지 않는 경우만 삽입
    }
  }
  
  show(hashTable);
  destructor(hashTable);
  system("pause");
  return 0;
}

  선형기법과 다르게 동일한 키값에 다른 데이터가 들어가있는것을 확인할 수 있다.

  체이닝 기법을 활용해 동일한 키값에 연결리스트로 들어갔다는 것을 확인할 수 있는 것이다.

레퍼런스

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

AVL트리

  AVL트리는 균형이 갖춰진 이진트리를 의미한다.

  완전이진트리는 검색에 있어서 O(logN)의 시간복잡도를 유지할 수 있다.

  AVL트리는 간단한 구현과정으로 특정 이진트리가 완전 이진트리에 가까운 형태를 유지하도록 해준다.

  AVL트리는 균형인수(Balance Facter)라는 개념을 이용한다.

  균형인수는 왼쪽자식높이에서 오른쪽자식높이를 뺀 절대값을 의미한다.

  이 균형인수가 ±1 이하인 경우가 AVL트리이다.

  균형인수가 범위를 벗어난 경우에는 회전(rotation)을 통해 재구성해야 한다.

  AVL트리의 각 노드는 균형인수를 계산하기 위한 목적으로 자신의 높이값을 갖는다.

  AVL트리는 4가지 형식에 의해 균형이 깨질 수 있다. 균형인수가 깨지는 노드를 X라고 했을 때

  4가지 형식은 다음과 같다.

  LL형식 : X의 왼쪽자식노드의 왼쪽에 삽입하는 경우

  RR형식 : X의 오른쪽자식노드의 오른쪽에 삽입하는 경우

  LR형식 : X의 왼쪽자식노드의 오른쪽에 삽입하는 경우

  RL형식 : X의 오른쪽자식노드의 왼쪽에 삽입하는 경우

AVL트리의 균형잡기

  AVL트리의 균형잡기는 각 노드가 삽입될 때마다 수행되어야 한다. 삽입과정에 소요되는 시간 복잡도는 O(logN)이다.

  따라서 각 트리의 균형잡기는 삽입시에 거치는 모든 노드에 대하여 수행된다는 점에서 O(1)의 시간 복잡도를

  만족해야 한다.

AVL트리의 삽입

  일반적인 이진탐색트리와 과정이 흡사하다. 다만 삽입시에 거치는 모든 노드에 대하여 균형잡기를 수행해줘야

  한다는 특징이 있다.

AVL트리의 출력

  삽입되는 과정을 면밀히 살펴보는것이 중요하므로 트리 구졸르 적절히 보여줄 수 있는 방식으로 출력해야 한다.

  일반적으로 트리의 너비가 높이보다 크다는 점에서 세로방향으로 출력하는 함수를 구현할 수 있다.

예제코드

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

int getMax(int a, int b){
  if(a > b) return a;
  return b;
}

typedef struct{
  int data;
  int height; //높이를 저장해야 시간 복잡도를 보장할 수 있다.
  struct Node* leftChild;
  struct Node* rightChild;
} Node;

int getHeight(Node* node){ //현재 특정한 루트노드에서의 높이값을 반환
  if(node == NULL) return 0; //노드가 없으니까 0을 반환
  return node->height;
}

void setHeight(Node* node){
  node->height = getMax(getHeight(node->leftChild), getHeight(node->rightChild)) + 1;
  //왼쪽, 오른쪽 중 더 큰 값에 + 1을 해준다.
}

int getDifference(Node* node){ //균형인수를 구하는 함수
  if(node == NULL) return 0;
  Node* leftChild = node->leftChild;
  Node* rightChild = node->rightChild;
  return getHeight(leftChild) - getHeight(rightChild);
}

Node* rotateLL(Node* node){
  Node* leftChild = node->leftChild; 
  //node의 왼쪽 자식노드를 leftChild로 정의
  
  node->leftChild = leftChild->rightChild; 
  //node의 왼쪽 자식노드를 leftChild로 정의한 노드의 오른쪽 자식노드로 변경
  
  leftChild->rightChild = node;
  //leftChild로 정의한 노드의 오른쪽 자식노드를 node로 변경.
  
  setHeight(node); //회전이후에 높이를 다시 계산
  return leftChild;
}

Node* rotateRR(Node* node){
  Node* rightChild = node->rightChild;
  node->rightChild = rightChild->leftChild;
  rightChild->leftChild = node;
  setHeight(node);
  return rightChild;
}

Node* rotateLR(Node* node){
  Node* leftChild = node->leftChild;
  node->leftChild = rotateRR(leftChild);
  setHeight(node->leftChild);
  return rotateLL(node);
}

Node* rotateRL(Node* node){
  Node* rightChild = node->rightChild;
  node->rightChild = rotateLL(rightChild);
  setHeight(node->rightChild);
  return rotateRR(node);
}

Node* balance(Node* node){ //균형잡는 함수
  int difference = getdifference(node); //균형인수
  if(difference >= 2){ //균형인수가 2이상인 경우에는 LL인지 LR인지 확인 후 처리 
    if(getDifference(node->leftChild) >= 1){
      node = rotateLL(node);
    }
    else {
      node = rotateLR(node);
    }
  }
  else if(difference <= -2){ //-2이하인 경우 RR인지 RL인지 확인 후 처리
    if(getDifference(node->rightChild) <= -1){
      node = rotateRR(node);
    }
    else{
      node = rotateRL(node);
    }
  }
  setHeight(node); //회전 이후에 높이를 다시 계산
  return node;
}

Node* insertNode(Node* node, int data){ //삽입함수
  if(!node){
    node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->height = 1; //초기 높이값을 1로 설정
    node->leftChild = node->rightChild = NULL;
  }
  else if(data < node->data){
    node->leftChild = insertNode(node->leftChild, data);
    node = balance(node);
  }
  else if(data > node->data){
    node->rightChild = insertNode(node->rightChild, data);
    node = balance(node);
  }
  else{
    printf("데이터 중복 발생.\n");
  }
  return node;
}

Node* root = NULL;

void display(Node* node, int level) { //출력함수
  if(node != NULL){
    display(node->rightChild, level + 1){ //가장 오른쪽 노드로 이동해서 오른쪽부터 출력하도록
    printf("\n");
    
    if(node == root){ //루트를 발견했을 때
      printf("Root : ");
    }
    
    for(int i = 0; i < level && node != root; i++){
      printf("        ");
      //가장 오른쪽으로 들어간 level값, 해당 노드의 레벨만큼 띄어쓰기를 해줌으로써
      //가장 깊은 노드가 가장 오른쪽에 출력되도록 한다.
    }
    
    printf("%d(%d)", node->data, getHeight(node));//해당값을 출력하고
    display(node->leftChild, level + 1);
    //왼쪽으로 재귀적으로 호출해서 기존 트리구조의 오른쪽 자식노드부터 출력하고
    //나중에 왼쪽자식노드가 출력될 수 있도록 한다.
  }
}

int main(void){
  root = insertNode(root, 7);
  root = insertNode(root, 6);
  root = insertNode(root, 5);
  root = insertNode(root, 3);
  root = insertNode(root, 1);
  root = insertNode(root, 9);
  root = insertNode(root, 8);
  root = insertNode(root, 12);
  root = insertNode(root, 16);
  root = insertNode(root, 18);
  root = insertNode(root, 23);
  root = insertNode(root, 21);
  root = insertNode(root, 14);
  root = insertNode(root, 15);
  root = insertNode(root, 19);
  
  display(root, 1);
  printf("\n");
  system("pause);
}

                                23(1)
                        21(2)
                                19(1)
                18(3)
                                16(1)
                        15(2)
                                14(1)
Root : 12(4)
                                9(1)
                        8(2)
                                7(1)
                6(3)
                                5(1)
                        3(2)
                                1(1)

  실행하면 이렇게 출력된다.

  처음 강의 들으면서 LL, RR, LR, RL 회전 그림을 보면서도 이해가 하나도 안되서 여기저기 찾아보고 코드 뜯어보면서

  이해했다.

  LL회전

    예제코드의 rotateLL에서 node가 A라고 할 때

    Node leftChild = node(A)->leftChild = B

    node(A)->leftChild = leftChild(B)->rightChild = E

    leftChild(B)->rightChild = node(A);

    이렇게 처리되는것이다.

  RR회전

    RR회전인 rotateRR은 LL의 반대이다.

    Node rightChild = node(B)->rightChild = A

    node(B)->rightChild = rightChild(A)->leftChild = E

    rightChild(A)->leftChild = node(B)

    LL의 반대이므로 LL 처리가 된 상태에서 RR을 처리한다면 다시 원래대로 돌아오는게 맞다.

  LR회전

    Node leftChild = node(A)->leftChild = B

    node(A)->leftChild = rotateRR(leftChild(B)) {

                                  Node rightChild = node(B)->rightChild = E

                                  node(B)->rightChild = rightChild(E)->leftChild(F)

                                  rightChild(E)->leftChild = node(B)

                                  return rightChild(E)

                                }

    return rotateLL(node(A)) {

               Node leftChild = node(A)->leftChild = E

               node(A)->leftChild = leftChild(E)->rightChild = G

               leftChild(E)->rightChild = node(A)

  RL회전

    Node rightChild = node(A)->rightChild = C

    node->rightChild = rotateLL(rightChild(C)) {

                                Node leftChild = node(C)->leftChild = D

                                node(C)->leftChild = leftChild(D)->rightChild = G

                                leftChild(D)->rightChild = node(C)

                                return leftChild(D)

                              }

    return rotateRR(node(A)) {

               Node rightChild = node(A)->rightChild = D

               node(A)->rightChild = rightChild(D)->leftChild = F

               rightChild(D)->leftChild = node(A);

             }

레퍼런스

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

이진탐색트리(Binary Search Tree)

  이진탐색(Binary Search)이 항상 동작하도록 구현하여 탐색속도를 극대화시킨 자료구조를 이진탐색트리라고 한다.

  이진탐색트리에서는 항상 부모노드가 왼쪽자식노드보다는 크고 오른쪽자식노드보다는 작다.

탐색방법

  여기서 37을 찾는다고 했을 때 루트노드인 30과 비교한다.

  그럼 찾는값보다 루트노드가 더 작기 때문에 더 큰값들이 있는 오른쪽 자식노드로 이동한다.

  오른쪽 자식노드인 48은 찾는값인 37보다 크기때문에 더 작은값인 왼쪽 자식노드로 이동한다.

  이와같이 한 노드의 값을 찾을 값과 비교하면 한쪽을 제외하고 검색할 수 있다.

  한번 확인할때마다 확인해야 하는 원소의 개수가 절반씩 줄어든다는 점에서 완전이진트리인 경우

  탐색시간에 O(logN)의 시간 복잡도를 갖는다.

이진탐색트리의 삭제

  1. 자식노드가 없는 경우

    삭제할 노드의 자식노드가 없는 경우 단순히 제거만 하면 된다.

  2. 자식노드가 하나만 존재하는 경우

    48처럼 하나의 자식노드를 갖고 있다면 삭제할 노드의 자리에 자식노드를 넣어준다.

    48을 삭제한다고 하면 37을 48의 위치로 바꿔주면 된다.

  3. 자식노드가 둘다 존재하는 경우

    위 그림에서 30처럼 자식노드가 둘다 존재한다면 삭제할 노드의 자리에 그 보다 큰 값들 중

    바로 다음으로 큰값을 넣어준다.

    30을 삭제한다면 다음으로 큰 값인 37을 30위치에 넣어준다.

예제코드

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

typedef struct{
  int data;
  struct Node* leftChild;
  struct Node* rightChild;
} Node;

Node* insertNode(Node* root, int data){ //특정 root에서 어떠한 노드를 삽입하고자 한다면
  if(root == NULL){ //그 루트가 NULL값이라면 해당 루트를 초기화
    root = (Node*)malloc(sizeof(Node));
    root->leftChild = root->rightChild = NULL;
    root->data = data;
    return root;
  }
  else{
    if(root->data > data){ //삽입하고자하는 데이터가 더 작다면 왼쪽으로 이동해서
                           //다시한번 노드를 삽입
      root->leftChild = insertNode(root->leftChild, data);
      //삽입된 결과를 자신의 왼쪽 자식노드에 넣어준다.
    }
    else{ //오른쪽 자식노드에 삽입된 결과를 넣어준다.
      root->rightChild = insertNode(root->rightChild, data);
    }
  }
  return root;
}

Node* searchNode(Node* root, int data){ //탐색
  if(root == NULL) return NULL;
  if(root->data == data) return root; //특정한 노드를 발견했다면 해당 노드 자체를 반환
  else if(root->data > data) return searchNode(root->leftChild, data);
  //해당 노드의 데이터보다 찾고자 하는 데이터가 더 작다면 왼쪽자식노드로 다시 탐색
  else return searchNode(root->rightChild, data);
  //데이터가 더 크다면 오른쪽자식노드로 다시 탐색
}

void preorder(Node* root){ //순회
  if(root == NULL) return;
  printf("%d ", root->data);
  preorder(root->leftChild);
  preorder(root->rightChild);
}


Node* findMinNode(Node* root) {//작은 노드를 탐색
  Node* node = root;
  while(node->leftChild != NULL){
    node = node->leftChild;
  }
  return node;
}

Node* deleteNode(Node* root, int data){//삭제함수
  Node* node = NULL;
  if(root == NULL) return NULL;
  if(root->data > data) root->leftChild = deleteNode(root->leftChild, data);
  //찾고자하는 데이터가 현재노드보다 작다면 왼쪽으로 탐색
  else if(root->data < data) root->rightChild = deleteNode(root->rightChild, data);
  //아니라면 오른쪽으로 탐색
  else{ //해당 노드가 데이터와 같다면
    if(root->leftChild != NULL && root->rightChild != NULL) { //자식노드가 두개 다 존재
      node = findMinNode(root->rightChild);//오른쪽 자식노드중 가장 작은값을 탐색
      root->data = node->data;//해당 노드의 데이터를 탐색한 값으로 변경
      root->rightChild = deleteNode(root->rightChild, node->data);
      //바꿔준 노드는 삭제.
    }
    else{//자식노드가 한개 이하일때
      node = (root->leftChild != NULL) ? root->leftChild : root->rightChild;
      //왼쪽 자식노드가 NULL이 아니라면 노드에 왼쪽 자식노드를 담고
      //NULL이라면 오른쪽 자식노드를 담는다.
      free(node);
      return node;
    }
  }
  return root;
}
    
int main(void){
  Node* root = NULL;
  root = insertNode(root, 30);
  root = insertNode(root, 17);
  root = insertNode(root, 48);
  root = insertNode(root, 5);
  root = insertNode(root, 23);
  root = insertNode(root, 37);
  root = insertNode(root, 50);
  root = deleteNode(root, 30);
  preorder(root);
  system("pause");
}

  삽입처리된 트리의 결과를 확인할 수 있다.

  원하는 값을 찾아 출력하는 예제코드는 아니다.

  root = deleteNode(root, 30);을 주석처리하고 실행하면

  출력값은 30 17 5 23 48 37 50 으로 출력되는데 위에 탐색방법에 있는 그림과 같은 형태다.

  preorder에서 처음에 루트값인 30을 먼저 출력하고 leftChild를 먼저 탐색하기 때문에 17 5 23이 출력되고

  그 다음 rightChild에서 48 37 50 이 출력된다.

  그리고 삭제함수를 포함해서 실행한다면 37 17 5 23 48 50이 출력된다.

  30을 삭제하고 그 바로 다음으로 큰 값인 37이 root로 올라오게 되는것을 확인할 수 있다.

  이진탐색트리의 성능을 최대로 끌어내기 위해서는 이진탐색트리가 완전 이진탐색트리에 가가워질수 있도록 설계

  해야 한다.

  트리를 사용하면 데이터를 처리함에 있어서 효율적이다.

  트리에서 데이터의 개수가 N개일 때 배열과 마찬가지로 O(N)의 공간만이 소요되며 삽입 및 삭제에 있어서

  일반적인 경우 기존의 배열을 이용하는 방식보다 효율적이다. 그래서 데이터베이스 등 대용량 저장 및 검색

  자료구조로 많이 사용된다.

  한쪽으로 치우친 편향 이진트리(Skwed Binary Tree)의 경우 탐색에 있어 O(N)의 시간 복잡도가 형성되므로

  기존의 배열을 사용하는 것 보다 오히려 많은 공간과 시간이 낭비된다.

  따라서 이진트리를 만들때는 트리의 균형이 맞도록 설정하는 것이 중요하다.

레퍼런스

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

너비우선탐색(Breadth First Search)

  너비우선탐색은 너비를 우선으로 하여 탐색을 수행하는 알고리즘이다.

  깊이우선탐색(DFS)와 마찬가지로 맹목적으로 전체노드를 탐색하고자 할 때 자주 사용되며

  큐(Queue)자료구조에 기초한다.

  너비우선 탐색은 고급 그래프 탐색 알고리즘에서 자주 활용된다.

  큐 자료구조에 기초한다는 점에서 구현이 간단하다.

  구현함에 있으서 큐STL을 사용하면 좋으며 탐색을 수행함에 있어서 O(N)의 시간이 소요된다.

  일반적인 경우 실제 수행시간은 DFS보다 좋은 편이다.

탐색과정

  탐색시작 노드를 큐에 삽입하고 방문처리한다.

  큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드들을 모두 큐에 삽입하고 방문처리한다.

  위 과정을 더이상 수행할 수 없을 때 까지 반복한다.

  이와같은 연결리스트가 있고 1부터 시작한다고 했을 때, 큐에 1이 먼저 들어가게 된다.

  그리고 1과 인접한 모든 노드를 큐에 넣어주면서 1은 빼준다.

  그 다음 2와 인접한 노드를 넣어주면서 2를 뺀다.

  3을 빼면서 3과 인접한 4,5를 큐에 넣는다

  8은 인접한 노드가 없으므로 큐에서 빼주기만한다.

  7을 빼면서 인접노드 6을 큐에 넣는다.

  4, 5, 6은 방문하지 않은 인접노드가 없으므로 큐에서 빼준다.

  그래서 방문순서 즉, 출력순서는

  1-2-3-8-7-4-5-6이 된다.

예제코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define INF 99999999
#define MAX_SIZE 1001

typedef struct{
  int index;
  struct Node *next;
} Node;
//연결리스트 정의

typedef struct{
  Node *front;
  Node *rear;
  int count;
} Queue;
//큐 정의

Node **a; //인접한 정점의 정보를 담아야 하니 이차원 포인터를 사용
int n, m, c[MAX_SIZE];
//정점, 간선, 방문정보

void addFront(Node *root, int index){ //연결리스트 삽입함수
  Node *node = (Node*)malloc(sizeof(Node));
  node->index = index;
  node->next = root->next;
  root->next = node;
}

void enQueue(Queue *queue, int index){ //큐 삽입함수
  Node *node = (Node*)malloc(sizeof(Node));
  node->index = index;
  node->next = NULL;
  
  if(queue->count == 0){
    queue->front = node;
  }
  else{
    queue->rear->next = node;
  }
  queue->rear = node;
  queue->count++;
}

int deQueue(Queue *queue){//큐 추출함수
  if(queue->count == 0){
    printf("큐 언더플로우 발생.\n");
    return -INF;
  }
  
  Node *node = queue->front;
  int index = node->index;
  queue->front = node->next;
  free(node);
  queue->count--;
  return index;
}

void bfs(int start){//너비우선 탐색 함수
  Queue q;
  q.front = q.rear = NULL;
  q.count = 0;//큐 초기화
  enQueue(&q, start);
  c[start] = 1;
  //방문처리
  
  while(q.count != 0){//큐에 아무것도 없을때까지 반복
    int x = deQueue(&q);
    printf("%d ", x); //추출한 원소 출력
    Node *cur = a[x]->next; //인접한 노드
    
    while(cur != NULL){
      int next = cur->index;
      if(!c[next]){ //방문하지 않은 상태라면
        enQueue(&q, next); //큐에 삽입
        c[next] = 1; //방문처리
      }
      cur = cur->next; //반복을 위해 next
    }
  }
}

int main(void){
  scanf("%d %d", &n, &m);
  a = (Node**)malloc(sizeof(Node*) * (MAX_SIZE));
  
  for(int i = 1; i <= n; i++){ //1부터 n까지의 정점에 대해 연결리스트 초기화
    a[i] = (Node*)malloc(sizeof(Node));
    a[i]->next = NULL;
  }
  
  for(int i = 0; i < m; i++){ //간선의 개수만큼 입력
    int x, y;
    scanf("%d %d", &x, &y); //연결되어있는 간선을 다 입력
    addFront(a[x], y); //연결리스트에 추가
    addFront(a[y], x);
  }
  
  bfs(1); //노드 1을 기준으로 너비우선탐색 실행
  system("pause");
  return 0;
}

  5 4

  1 2

  1 3

  1 5

  2 5

  이렇게 입력하면

  1 5 3 2가 출력된다.

  5개의 정점과 4개의 간선이 있도록 하고

  각 노드를 만들며 next를 NULL로 초기화한다.

  연결리스트에 추가하는 부분을 보면 a[x], y와 a[y], x가 있는데 a[1], 2, a[2], 1 이 형태로 들어간다고 가정하고

  처리를 본다면

  node->index = 2

  node->next = root(a[1])->next(NULL) = NULL

  root(a[1])->next = node(index2)

  node->index = 1

  node->next = root(a[2])->next(NULL) = NULL

  root(a[2])->next = node(index1)

  이런 식으로 2와 1을 서로 인접한 노드로 만들어주는 것이다.

  그림으로 보면 다음과 같다.

  1부터 시작한다고 했으니 큐에 처음 1을 넣어준다음 방문처리를 한다.

  그리고 반복문으로 큐에 아무것도 남지 않을때까지 반복하도록 하고 큐에 담겨있는 원소를 추출한다.

  그럼 제일 먼저 시작 노드인 1이 빠져나오면서 출력되고 1의 인접노드를 cur에 담아 내부 반복문을

  수행한다. 내부반복문에서는 해당 노드의 모든 인접 노드를 방문하며 큐에 삽입해주고 방문처리를 한다.

  그럼 5, 3, 2순서로 큐에 들어가게 되고 다시 deQueue로 하나 추출한 다음 그 노드의 인접노드를 체크한다.

  여기서는 이미 1을 제외한 모든 노드인 5, 3, 2를 다 방문해서 큐에 넣어뒀기 때문에 체크만 하고

  하나씩 출력하게 된다.

  노드 1의 연결 순서가 5, 3, 2가 되는것은 연결리스트로 처음 들어간 2가 다음에 들어온 3의 next가 되고

  3은 그 뒤에 들어온 5의 next가 되기 때문이다.

레퍼런스

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

깊이우선탐색(Depth First Search)

  깊이우선탐색은 탐색을 함에 있어서 보다 깊은것을 우선적으로 하여 탐색하는 알고리즘이다.

  깊이우선탐색은 기본적으로 전체 노드를 맹목적으로 탐색하고자 할 때 사용하며

  스택(Stack) 자료구조에 기초한다.

  빠르게 모든 경우의 수를 탐색하고자 할 때 쉽게 사용할 수 있으며

  다음과 같은 알고리즘에 따라 구현할 수 있다.

  탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.

  스택의 최상단 노드에게 방문하지 않은 인접노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리를 한다.

  방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다.

  위 과정을 더이상 수행할 수 없을 때 까지 반복한다.

깊이우선탐색 수행과정

  이러한 형태의 그래프를 탐색하며 1부터 출발한다고 가정한다.

  1부터 출발하면 1에서 연결된 노드 중 방문하지 않은 2를 방문하고 2에서도 방문하지 않은 7을 방문한다.

  7에서는 6을 방문하는데 6의 경우는 연결된 노드가 없기 때문에 스택에서 제거하고 7에 연결된 8을 방문한다.

  8은 1과 연결되어있으며 방문하지 않은 인접노드가 없기 때문에 8, 7, 2를 스택에서 제거한다.

  1에서 방문하지 않은 인접노드인 3을 방문하고 3은 4를 4는 5를 방문한 뒤 더이상 방문할 인접노드가 없기에

  스택을 비워준다.

  스택 형태로 보면 다음과 같다.

  방문순서를 정리해보면 1 2 7 6 8 3 4 5순서이다.

  스택자료구조에 기초한다는 점에서 구현이 간단하지만 실제로는 스택을 쓰지않아도 재귀함수를 이용하면 기본적으로

  스택과 비슷하게 동작한다는 점에서 재귀함수로 간단히 구현할 수 있으며 탐색을 수행함에 있어서 O(N)의 시간이

  소요되는 전수탐색 알고리즘이다.

import java.io.*;
import java.util.*;

public class Graph{
  private int V;//노드의 개수
  private LinkedList<Integer> adj[];//인접리스트
  
  Graph(int v){
    V = v;
    adj = new LinkedList[v];
    
    for(int i = 0; i < v; ++i){//인접리스트 초기화
      adj[i] = new LinkedList();
    }
  }
  
  void addEdge(int v, int w){
    adj[v].add(w);
    
    /*
      연결된 리스트 확인
      for(int i = 0; i < adj.length; i++){
        System.out.println("adj["+i+"] : "+adj[i]);
      }
    */
  }
  
  void DFSUtil(int v, boolean visited[]){
    //현재 노드를 방문한것으로 표시하고 값을 출력.
    visited[v] = true;
    System.out.print(v + " ");
    
    //방문한 노드와 인접한 모든 노드를 가져온다.
    Iterator<Integer> i = adj[v].listInteger();
    while(i.hasNext()){
      int n = i.next();
      /*
        다음값인 n의 값 확인
        System.out.println("i.next : "+n);
      */
      
      //방문하지 않은 노드면 해당 노드를 시작 노드로 다시 DFSUtil 호출
      if(!visited[n]){
        DFSUtil(n, visited);
      }
    }
  }
  
  void DFS(int v){
    //노드의 방문여부 판단 (초기값 : false)
    boolean visited[] = new boolean[V];
    
    //v를 시작노드로 DFSUtil 순환 호출
    DFSUtil(v, visited);
  }
  
  /*
  비 연결형 그래프일 경우
  void DFS(){
    //노드의 방문여부 판단
    boolean visited[] = new boolean[V];
    
    //모든 정점을 하나씩 방문
    for(int i = 0; i < V; ++i){
      if(visited[i] == false){
        DFSUtil(i, visited);
      }
    }
  }*/
  
  public static void main(String[] args){
    Graph g = new Graph(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);
    
    g.DFS(2);
    //DFS(); 비연결형그래프
  }
}

  강의에서 본 C예제코드는 이해가 많이 떨어져서 java코드로 예제를 찾아 학습했다.

  위 코드의 결과값은 2 0 1 3이 출력된다.

  스택을 이용한 구현이 아닌 재귀함수를 이용한 구현이다.

  addEdge는 노드를 연결해주는 것인데 다 연결되고나면

  adj[0] = [1, 2]

  adj[1] = [2]

  adj[2] = [0, 3]

  adj[3] = [3]

  이런 형태가 된다.

  그림으로 본다면

  이렇게 연결된 그래프형태다.

  연결까지 다 처리되고 나면 DFS로 시작노드를 넘겨주면서 처리하게 되는데 visited[]는 boolean형태로 V만큼의 크기를

  설정함으로써 adj배열과 같은 크기로 설정해준다.

  이때 모든 기본값은 false가 된다.

  DFSUtil에서는 v와 visited를 넘겨 처리해준다.

  처음 넘겨주는 노드는 2로 임의로 정한건데 visited[2] = true를 해줌으로써 2번 노드는 방문했다는것을 확인할 수

  있도록 한다.

  방문한 노드는 우선적으로 출력을 해주고 Iterator로 방문한 노드와 인접한 모든 노드를 가져온다.

  이 경우 adj[2] = [0, 3]이기 때문에 0과 3을 가져온다.

  연결되어있는 다음노드가 존재한다면 반복문을 실행하고 n에 next값을 넣어준다.

  그럼 n은 0이 되고 visited[0]은 아직 방문하지 않은 false상태이기 때문에 DFSUtil함수를 호출하게 된다.

  이렇게 계속 재귀적으로 반복하며 모든 노드를 방문하도록 수행한다.

레퍼런스

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

● gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html