r그래프, 트리, BFS, DFS

in CS on Algorithm, 알고리즘, 그래프, 트리, Bfs, Dfs


정말 내가 많이 헷갈리고, 코드로 이용 못하는 그래프다.

먼저, 나는 공부를 정말 대충했기 때문에 트리가 그래프에 속하는 자료구조라는 것 외에는 아무것도 몰랐다. 정말 지금 다시 보면 멍청하기 그지없다. 그래서 먼저 트리와 그래프의 정확한 정의와 그 차이에 대해서 보려고 한다.

그래프

일부 객체의 쌍들이 서로 연관된 객체의 집합을 이루는 구조이다. 즉 객체(노드)들과 객체들과의 관계(간선)이 있는 구조이다. 일련의 꼭짓점들과 꼭짓점을 잇는 변들로 구성된 조합론적 구조로 볼 수 있다.

  1. 두개의 정점 사이에 2개 이상의 경로가 가능하다. 노드들 사이에 양방향 경로를 가질 수 있다.
  2. 사이클이 존재(loop가 존재)한다.
  3. 루트 노드, 부모-자식 노드라는 개념이 없다.
  4. 순회는 DFS, BFS로 이루어진다.
  5. 그래프는 cyclic / acyclic 이다.
  6. 방향 그래프 / 무방향 그래프가 있다.
  7. 네트워크 모델

용어

  • 버텍스(Vertex) : 노드
  • 아크(=Edge) : 간선
  • In-degree : 다른 버텍스에서 오는 아크의 개수
  • Out-degree : 다른 버텍스로 가는 아크의 개수

구현 방식

  1. 인접 리스트
[1] -> 2 -> 3
[2] -> 1 -> 3 -> 4
[3] -> 1 -> 2 -> 4 ->5

노드에 연결되어 있는 노드들을 리스트로 표현한 것이다. 방향, 가중치 그래프에서 연결 되어 있는 상황을 인접리스트로 표현할 수 있다.

간선 정보만을 저장해서 O(E)의 공간을 요구하여 공간 효율성이 우수하지만 두 정점이 서로 연결되어 있는지 확인하려면 O(V)의 시간을 요구한다.

  1. 인접 행렬

무방향 그래프에 가중치가 없는 그래프일 경우 인접행렬로 표현할 수 있다.

모든 정점들의 연결여부를 저장해서 O(V^2)의 공간이 요구되어 공간 효율성이 떨어지지만 두 정점이 서로 연결되어 있는지 확인하기 위해 O(1)의 시간이 요구된다.

트리

트리는 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 한다.

  1. 트리는 그래프의 특별한 케이스로, 최소연결트리 라고 불린다. 두개의 정범 사이에 반드시 1개의 경로만 가진다.
  2. 사이클이 존재하지 않다.(loop 없음)
  3. 부모-자식 관계가 존재 => top-bottom / bottom-top 으로 이루어진다.
  4. 순회는 전순위, 중순위, 후순위로 이루어진다. 이 세가지는 모두 DFS/BFS 안에 있다.
  5. 트리는 DAG(Directed Acyclic Graphs), 사이클이 없는 방향 그래프이다.
  6. 간선은 항상 노드의 개수-1 만큼 가진다.
  7. 계층 모델

쓰이는 기본 용어는 다음과 같다.

  • 차수(edge) : 노드가 가지고 있는 자식 노드의 개수, 즉 연결하는 선의 개수가 된다. 각 노드마다 다르다. 트리의 차수는 트리가 가지고 있는 노드의 차수중 가장 큰 차수이다.
  • 레벨(level) : 각 층에 번호를 매기는 것. 루트의 레벨은 1, 자식으로 갈수록 레벨이 증가한다.
  • 높이(height) : 트리가 가지고 있는 최대 레벨

트리는 크게 “Binary Tree”, “Non-Binary Tree”로 나뉜다.

이진트리는 각 노드에 대해 두개 이하의 자식을 가지고, non binary tree는 노드 자식 개수에 제한이 없다는 뜻이다.

표현법

  1. 배열 표현법 : 주로 포화 이진트리, 완전 이진 트리의 경우 많이 쓰인다. 비어 있는 부분이 중간에 많이 발생하면 메모리 공간의 낭비가 발생한다.
    A
   B  C
  D E F G
  
0  1  2  3  4  5  6  7

   A  B  C  D  E  F  G

부모와 자식의 인덱스 사이의 관계

  • 노드 i의 부모 노드 인덱스 : └i/2┘
  • 노드 i의 왼쪽 자식 노드 인덱스 : i*2
  • 노드 i의 오른쪽 노드 인덱스 = i*2 + 1
  1. 링크 표현법 : 노드가 구조체로 표현되고, 각 노드가 가진 포인터를 이용해 노드와 노드를 연결하는 방법이다. 데이터 필드 하나와 양쪽 노드 각각을 가리키는 2개의 포인터 필드를 가진다.

순회

이진 트리를 순회한다는 것은 이진 트리에 속하는 모든 노드를 한 번씩 방문하여 목적에 맞게 처리하는 것을 의미한다.

  • 전위 순회(preorder) : root 왼 오
  • 중위 순회(inorder) : 왼 root 오
  • 후위 순회(postorder) : 왼 오 root

그냥 앞에 들어가는 글자를 중간에 방문한다고 생각하면 된다.

항상 서브 트리는 왼쪽을 오른쪽보다 먼저 방문한다.

  • 레벨 순회 : 각 노드를 레벨 순으로 검사하는 방법이다. 앞의 순회들은 순환호출을 해서 간접적으로 스택을 사용했는데, 레벨 순회는 큐를 사용한다. 레벨 순회는 큐에 하나라도 노드가 있으면 계속 반복한다.

“non-binary tree”

가장 대표적인 사용예는 “trie” 자료구조라고 할 수 있다. 이 자료구조는 문자열 검색에 많이 사용된다. trie에서 단점을 공간 복잡도라고 하는데, 그 이유는 모든 노드마다 자식들 노드를 가리키는 포인터를 들고 있어야 하기 때문이다.

이는 노드 별 자식을 linked list 형태로 표현하면 해결이 가능하다고 한다.

문자열을 찾는거나, 컴퓨터의 파일 시스템과 같은 경우에도 사용될 수 있다.

“binary tree”

이진 트리는 각 노드의 자식을 2개 이하로 가지고 있다. 모든 노드가 2개의 서브 트리를 가지고 있으므로 순환적으로 정의된다.

이진트리는 노드를 하나도 갖고 있지 않을 수 있지만, 일반 트리는 노드를 1개 이상을 가지고 있어야 한다.

이진트리는 형태에 따라 포화이진트리, 완전이진트리로 나눌 수 있다.

  • 포화 이진 트리 : 각 레벨에 노드가 꽉 차 있는 이진 트리.
  • 완전 이진 트리 : 높이가 k일 때, 레벨 1부터 k-1까지는 노드가 채워져 있고, 마지막 레벨에는 노드가 꽉 차 있지 않아도 되는 트리

BST, Binary-Search-tree

이진탐색트리이다. 유명하고, 접근성이 용이하다. 각 노드는 왼쪽 자식 트리와 오른쪽 자식 트리를 가지는 루트를 자식으로 가지고, 왼쪽 서브 트리는 루트보다 작은값을, 오른쪽 서브 트리는 루트보다 큰 값을 가지는 형태의 이진트리를 말한다.

BST는 자료의 입력, 삭제, 탐색 모두 시간 복잡도가 O(logN) 이다. 배열 이진 탐색의 경우 시간 복잡도는 동일하지만 자료의 변경, 삭제가 불가능했다. 또한 BST를 linked list로 구현할 경우 탐색에서 O(N)의 시간이 소요된다.

시간의 복잡도가 왜 O(logN)이 되나면, 이진 탐색 트리에서 최대 탐색 횟수는 트리의 depth이다.

n개의 노드가 주어질 때, 매 depth에서 2의 노드씩으로 분할이 되기 때문에, 2^depth = N이 되고,

time = depth = logN이 된다.

Segment tree

tree를 이용해서 구획을 나누는 방법이다.

BFS, 너비 우선 탐색

이제 트리와 그래프의 차이는 좀 봤으니 그래프의 탐색 방법인 BFS와 DFS를 보겠다. 그래프에서 탐색은 모든 노드를 한 번씩 탐색하기 위해서이다.

BFS는 루트부터 시작해서 인접한 노드, 가로방향으로 탐색한다고 이해하면 편하다.

시작 정점에서 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문한다. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용한다. 따라서 BFS는 시작점과 연결된 모든 정점을 방문하는 완전탐색이다.

BFS는 그래서 가중치없는 그래프에서 최단 경로를 찾아줄 수 있다.

예) 모든 친구 관계를 그래프로 표시한 다음, A와 B 사이에 존재하는 경로를 찾는 경우.

깊이 우선 탐색의 경우 모든 친구 관계를 다 봐야 할 지도 모르지만, 너비 우선 탐색의 경우 A와 가까운 관계부터 본다.

특징

BFS는 재귀적으로 동작하지 않는다. 구현할 때는 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. 그렇지 않으면 무한 루프에 빠질 수 있다.

BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐를 사용한다. 선입선출.

인접리스트로 구현된 경우에는 O(V+E), 인접 행렬로 구현했을 경우 O(V^2)의 시간 복잡도가 걸린다.

구현 방법

  1. 인접 행렬 시간 복잡도 : O(V^2)

2차원 배열을 사용한다. 그런데 시간이 오래 걸리기 때문에 사용을 잘 안한다.

  1. 인접 리스트 시간 복잡도 : O(V+E)

링크드 리스트를 사용한다. 연결 리스트를 구현하면 좋지만, 매번 구현하기 귀찮으니 C++에서는 vector, java에서는 ArrayList를 사용한다.

C++이 더 익숙하니 C++로 해보자.

  #include <iostream>
  #include <vector>
  #include <queue>
  
  #define max_int 10001
  
  using namespace std;
  
  /*
  시간 복잡도 : O(n+m)
  공간 복잡도 : O(n)
  사용한 알고리즘 : BFS
  사용한 자료구조 : 인접 리스트, 배열
  */
  
  int n, m, k, a, b, check[max_int];
  
  vector<int> v[max_int];
  
  void bfs(){
    queue<int> q;
    check[k] = 0;
    q.push(k);
    
    while(!q.empty()){
      int node = q.front();
      q.pop();
      
      for(int i=0; i<v[node].size(); i++){
        int next = v[node][i];
        
        if(check[next] == -1){
          check[next] = check[node] + 1;
          q.push(next);
        }
      }
    }
  }
  
  int main(){
    // 1. 입력
    // n 정점의 수, m 간선의 수, k 시작점의 번호를 입력 받습니다.
    scanf("%d %d %d", &n, &m, &k);
    
    // 2. 초기화
    // 거리 정보를 저장할 check 배열을 -1로 초기화합니다.
    // 무엇으로 초기화 할지는 개인의 취향입니다.
    for(int i=0; i<=n; i++) check[i] = -1;
    
    // 3. 간선 저장
    for(int i=0; i<m; i++){
        // 간선의 정보를 입력받고
        scanf("%d %d", &a, &b);
        // 중요, 무 방향그래프를 양방향 그래프로 만들어줍니다.
        v[a].push_back(b);
        v[b].push_back(a);
    }
    
    // 4. 너비 우선 탐색 수행
    bfs();
    
    // 5. 출력
    for(int i=1; i<=n; i++){
        printf("%d\n", check[i]);
    }
}

출처 : https://velog.io/@skyepodium/BFS%EB%8A%94-%EB%82%AF%EC%84%A4%EC%96%B4%EC%84%9C

와 근데 보는데 velog를 쓰신 분은 내가 어떤 키워드를 검색해도 다 나오고, 설명도 정말 잘하신다. 깊게 넓은 분야를 공부하셨다는 게 보여서 멋있다.

경로 추적

시작점에서 도착점까지의 경로를 추적할 수 있다. 다음 정점을 방문할때 이전의 정점의 정보를 저장하면 된다.

for(int i=0; i<v[node].size(); i++){
  int next = v[node][i];
  if(check[next] == -1){
    check[next] = check[node] + 1;
    from[next] = node; // 이전 정점의 정보를 from 배열에 넣어준다.
    q.push(next);
  }
}

이러면 이제 도착점에서 시작점까지 역추적할 수 있다. velog의 저자분께서는 무언가 거꾸로 할 때는 스택을 이용하는 게 좋다고 하셨다. 재귀를 사용해도 좋다. 재귀가 내부적으로 스택으로 이루어져있기 때문이다.

void tracing(int node){
  if(node == k) return;
  int next = from[node];
  tracing(next);
  printf("%d ", next);
}

위와 같은 정보를 저장하기 위해 배열을 2개 사용하는 경우가 있다. 하지만 두 배열 보두 방문했음을 저장하기 때문에,

check 배열과 같이 배열 하나로 방문했음과, 더 나아가서 특정 정점까지의 거리도 저장할 수 있는 배열을 만들 수 있다.

DFS, 깊이 우선 탐색

깊이 우선 탐색은 최대한 깊이 파고든다고 생각하면 된다. BFS는 queue로 구현하지만, DFS는 stack으로 구현한다.

기본 작동 방식은 stack을 이용해서 갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아가는 것이다.

stack과 재귀 함수를 이용해서 구현한다. 보통 DFS가 BFS보다 간단하다. 단순 검색 속도는 BFS에 비애 느리다.

구현 방법

BFS와 다르게, BFS는 큐에 넣을 시점에 해당 노드를 방문했다고 체크해야 하지만 DFS는 일단 들어가서 체크한다.

  1. 인접 행렬
void dfs(int x){
  check[x] = true;
  
  for(int i=1; i<=V; i++){
    if(graph[x][i] == 1 && !check[i])
      dfs(i);
  }
}

DFS 한번에 V번 반복하기 때문에 O(V) 만큼 시간이 필요하고, V개의 정점을 모두 방문하기 때문에 O(V^2)

  1. 인접 리스트
void dfx(vector<int> *graph, bool *check, int x){
  check[x] = true;
  
  for(int i=0; i<graph[x].size(); i++){
    int next = graph[x][i];
    if(!check[next])
      dfs(next);
  }
}

모든 정점과 간선을 한번씩 검사하므로 O(V+E).

#include <iostream>
#include <vector>

using namespace std;

int number = 9;
int visit[9];
vector<int> a[10];

void dfs(int start){
  if(visit[start]){
    return;
  }
  
  visit[start] = true;
  
  for(int i=0; i<a[start].size(); i++){
    int x = a[start][i];
    dfs(x);
  }
}

int main(void){
  a[1].push_back(2);
  a[2].push_back(1);
  
  ...
  
  dfs(1);
  
  return 0;
}