자료구조 (10), Graph

자료구조 (10), Graph

2022. 6. 21. 02:32ㆍ강의 내용 정리/자료구조

728x90

Graph

1. 그래프

1) 그래프란?

- 노드들의 연결관계를 표시하는 엣지의 집합으로 포함되는 자료구조이다.

- 트리는 노드와 엣지의 연결관계가 있고, 한 노드에서 다른 노드로 갈 때의 경로가 유일해야한다. 그래프는 그보다 더 상위의 개념으로 연결관계만 있으면 된다. vertex는 노드와 같은 개념이다.

- n은 대부분 입력되는 데이터의 개수를 의미한다.

- 방향성을 가지냐는 것도 중요하다. 이를테면 a, b가 입력됐을 때 a에서 b로 갈 수 있는지, b에서 a로 갈 수 있는지, 양방향으로 모두 갈 수 있는지를 알아야지 그래프의 모양을 그릴 수 있다. undirect 그래프는 양방향이다. 일반적으로 undirect는 링크라는 표현을 direct는 엣지라는 표현을 많이 사용한다.

- direct 그래프는 입력되는 순서도 중요하다. (a, b) or (b, a) 이때 a, b로 입력하면 일반적으로 a에서 b로 간다는 것을 의미한다.

2) Graph terminology

(1) adjcent nodes

- 서로 연결되어있을 때 인접하다고 한다. 방향성이 있다면 이를 고려해야한다.

(2) path

- 노드들의 집합으로 두 개의 노드가 연결되어있는 것을 나열한다.

(3) complete graph

- 모든 노드들에 대해 가능한한 모든 엣지를 가지는 것을 의미한다. 이에 따라 complete binary tree와는 살짝 다른 특징을 가진다. n개의 노드를 가진다면 엣지는 n * (n-1)(direct), n * (n-1) / 2(undirect)만큼 가진다. n개의 노드에 대해 자기 자신을 제외한 모든 노드에 연결이 되어야하기에 그러하다.

(4) weighted graph

- 엣지에 가중치를 부여해서 실생활의 데이터를 추상화하는 것이 가능하다. 거리나 시간을 입력해 이를 구할 수 있다.

3) 특화되어있는 자료구조

(1) 트리와 그래프의 복잡도가 동일할 때

- 그래프 전체에 적용할 수 있는 알고리즘이 더 넓은 범위에 대해서 다룰 수 있다. 왜냐하면 트리는 그래프의 특징을 가지고 있지만 트리에만 한정지어서 처리할 수 있는 조금 더 특화되어있는 부분이 있다.

(2) direct와 undirect의 복잡도가 동일할 때

- undirect로 표현되어있는 그래프는 direct로 표현이 가능하다. 이를 양쪽을 가리키는 엣지형태로 변환하면 direct로 처리가 가능하다. 따라서 undirect그래프는 direct로도 처리가 가능하다.

- 반면 반대의 경우에는 불가능하다. undirect 그래프는 조금 더 특수한 범위(좁은 범위)에 대해 처리가 가능한 그래프다. 결국 undirect 그래프는 direct 그래프이지만 모든 엣지가 시작, 종료지점이 있으면 종료지점에서 시작지점으로 갈 수 있는 그래프이다.

(3) weighted, unweighted 그래프

- unweighted 그래프는 조금 더 좁은 범위에 대해 처리할 수 있는 그래프이다. 이를 weighted로 바꿔서 처리가 가능하기 때문이다.

따라서 가장 범용적으로 우수한 그래프의 알고리즘은 direct weighted 그래프이다.

4) 그래프를 구현하기 위한 방식

(1) 인접 행렬

- 노드 집합을 1차원으로 가지고 있고, 2차원의 엣지 배열은 도착지에 대해 구현할 수 있다.

- 인접 행렬이 대칭형이면 undirect 그래프이다.

- 그래프의 덴시티는 노드가 있을 때 엣지가 얼마나 있는지에 따라 다르다. 따라서 가장 밀접도가 높은 그래프는 complete 그래프이다. 밀접도가 최소인 경우에는 n-1이다. 이는 트리가 된다.

- 인접행렬을 사용하면 랜덤 액세스를 할 수 있다. 따라서 어디로 연결이 되어있는지를 확인할 수 있어서 매우 큰 장점을 가진다. 따라서 밀접도가 높으면 인접행렬이 효율적이다. 빈 공간이 많으면 인접 리스트가 효율적이다.

- 노드 백만개의 그래프에서 a에서 b의 엣지를 보고싶다면 바로 확인이 가능하다.

(2) 인접 리스트

- 링크드 리스트로 구현한다.

- 리스트의 시작 부분을 가지고 있고, 인접한 노드를 연결해놓는다.

- 밀접도가 낮으면 인접 리스트가 유리하다.

- 어떤 특정 노드에 연결되어있는 모든 노드를 탐색해야하고, 이 노드의 연결 노드를 탐색해야한다면 인접 리스트가 유리하다.

5) 그래프 탐색 방법

(1) BFS(WFS)

- BFS는 최고우선탐색이 있어서 이 대신 WFS를 사용하는 경우가 많다.

- 어떤 노드에서 시작해서 다른 노드를 방문할 때 이를 어떤 순서로 진행하는지, 항렬이 높은 순서로 탐색한다고 생각하면 된다.

- 내부에 queue를 사용한다.

- 사이클이 있는 경우 다시 자기 자신으로 돌아오는 경우가 있기에 방문처리(marked)를 해줘서 재방문을 막는다.

- 내부에 queue를 사용하면 BFS이다. (너비우선탐색, best는 아니다.)

- bfs는 동일한 레벨에 대해 처리한다.

(2) DFS

- 자식이 높은 순서로 탐색한다고 생각하면 된다.

- 내부에 stack을 사용한다.

- 사이클이 있는 경우 다시 자기 자신으로 돌아오는 경우가 있기에 방문처리를 해줘서 재방문을 막는다.

- DFS는 재귀적으로 구현할 수 있다. 함수의 호출이 콜스택에 쌓이기 때문에 스택과 같이 사용할 수 있기 때문이다.

- 연결되어있는 vertex를 얻기 위해 getToVertex를 사용한다.

- 언젠가 도달할 가능성이 있다면 유망하다라고 얘기하지만 그게 아니라면 유망하지 않다고 판단한다. 유망성을 판단하는 기준은 탐색할 노드가 남아있지 않은데 더이상 자식 노드가 없는 경우에는 유망성이 없다고 판단한다. 유망성을 판단하여 프루닝(가지치기)을 해 중간에 탐색을 멈출수도 있다. ex) 부모 노드가 자식 노드보다 크다라는 것을 보장하면 탐색할 숫자가 자식노드보다 크면 굳이 탐색할 필요가 없다.

6) Single source Problem

- single source인 경우는 하나의 시작 도시에서 다른 도시까지 가는 경우를 의미한다. 즉, source, destination이 있어 출발지와 목적지가 존재하는 경우이다.

- Single-source shortest-path 문제는 시작점부터 도착지까지의 경로 중 최단 경로를 의미한다. 다익스트라 알고리즘으로 문제를 해결할 수 있다. weightless인 경우, 혹은 모든 가중치가 동일한 경우에는 도착지까지 도달한 엣지의 개수로 거리를 판단하기에 선입선출을 보장하는 BFS로도 가능하다.

2. ADT Set definitions

- set: 중복 원소가 없고 순서가 없기에 정렬되지 않는다. 이에 따라서 정렬된 상태로 무언가를 처리해주고자 한다면 안될 수 있다.

- 명시적으로 구현할 때 비트백터를 이용해 구현할 수 있다. boolean operation을 활용해 이를 구현할 수 있다. 이때 존재하는 경우에는 1, 존재하지 않는 경우에는 0으로 구현한다.

- 묵시적으로 구현할 때 리스트를 이용해 구현할 수 있다.이때는 ADT List operation을 활용해 이를 구현할 수 있다.

- set은 정렬되지 않는데 묵시적으로 표현하는 방식에서 sorted list를 자료구조로 삼는 것이 왜 더 좋은 선택이 될까? 사실 중복하게 설정도 가능하긴하지만 왜 그런지 한번 생각해보자.