CS/자료구조론

그래프 (Graph)

망재이 2024. 2. 9. 18:58
그래프의 정의

 

- 그래프 : 공집합이 아닌 정점의 집합과 간선의 집합으로 구성되는 자료구조

 

  • 무방향 그래프 (undirected graph)
    - 간선을 나타내는 정점의 쌍에 순서가 없음
    - 정점 A와 B를 연결하는 간선 (A, B)와 간선 (B, A)는 같은 간선으로 취급
    - n개의 정점을 가진 무방향 그래프에서 최대 간선수는 n(n - 1) / 2개

  • 방향 그래프 (directed graph)
    - 정점 A에서 출발하여 B로 연결되는 간선은 <A, B>
    - n개의 정점을 가진 방향 그래프에서 최대 간선수는 n(n - 1)개

 

 

 

 

그래프의 표현

 

  • 그래프의 인접행렬 표현
    - 그래프 내의 정점에 다른 임의의 정점과의 여부를 표현하는 방법
    - 인접행렬의 크기는 정점의 수가 n일 때 n^2
    - 무방향성 그래프의 인접행렬에서는 대각선에 대해 선대칭이며, 1의 수는 간선의 수의 2배

* 그래프의 인접행렬 표현

1. 그래프 G1(V, E)

   V(G1) = {0, 1, 2, 3}

   E(G1) = {(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)}

  0 1 2 3
0 0 1 1 1
1 1 0 1 0
2 1 1 0 1
3 1 1 1 0

 

2. 그래프 G2(V, E)

   V(G2) = {0, 1, 2, 3}

   E(G2) = {<0, 1>, <0, 2>, <0, 3>, <1, 2>, <1, 3>, <2, 3>}

  0 1 2 3
0 0 1 1 1
1 0 0 1 1
2 0 0 0 1
3 0 0 0 0

 

 

  • 그래프의 인접리스트 표현
    - 어느 정점에 인접한 정점들을 하나의 노드로 구성하고, 이 인접한 노드들을 연결리스트로 표현
    - 무방향 그래프의 각 정점의 차수는 그 정점에 대한 인접리스트에 속한 노드들의 수 = 각 정점에 연결된 간선의 수

 

 

 

 

 

그래프의 순회

 

  • 깊이우선순회(depth first traversal)
    - 하나의 정점에서 다른 정점으로 이동하되 더 이상 깊이 들어갈 수 없을 때까지 이동한 다음 마지막 정점에서 더 이상 방문할 지점이 없으면 이전 정점으로 돌아와 다음 정점을 방문하는 탐색 알고리즘
    - 방문하는 순서대로 정점을 스택에 쌓고, 방문이 끝나면 스택에서 pop하는 형태로 구현

  • 너비우선순회(breadth first traversal)
    - 시작 정점을 방문한 후 시작 정점과 인접한 정점들을 우선적으로 방문하는 방식으로 임의의 정점을 방문하면 해당 정점의 인접한 정점을 우선적으로 방문하는 방식의 탐색 알고리즘
    - 각 정점을 방문할 때마다 모든 인접 정점들을 검사하고 이 중 처음 보는 정점을 발견하면 방문 예정이라고 기록해둔 뒤, 모든 인접 정점을 검사한 후 방문
    - 큐의 성질을 활용하여 먼저 넣은 점점을 항상 먼저 방문
더보기

Q. 다음 그래프를 너비우선탐색, 깊이우선탐색 방법으로 방문할 때 각 정점을 방문하는 순서로 옳은 것은? (단, 둘 이상의 정점을 선택할 수 있을 때는 알파벳 순서로 방문한다.)

1. BFS : ABFCED / DFS : ABCDEF

2. BFS : ABCDEF / DFS : ABFCED

3. BFS : ABFCDE / DFS : ABCDEF

4. BFS : ABCDEF / DFS : ABCDFE

 

-> A에서 출발한다고 가정했을 때

BFS는 A에서 B, F를 차례로 방문한다. B에서 C로 방문한다. F에서 D, E를 차례로 방문한다. (ABFCDE)

DFS는 A에서 B와 F를 방문할 수 있는데 알파벳 순서로 B로 방문한다. B에서 C와 F를 방문할 수 있는데 알파벳 순서로 C로 방문한다. 이러한 과정을 거치면 ABCDEF 순서로 방문하게 된다.

 

 

 

 

 

최소 비용 신장트리 (MST; Minimum Spanning Tree)

 

  • 최소 비용 신장트리
    - 가중치 그래프에서 신장트리가 여러 개 있을 수 있는데, 그 중 모든 간선의 길이의 합이 최소인 것
    - 그래프 G의 신장트리는 그래프 G 내의 모든 정점이 포함하고 간선의 수가 n - 1개인 사이클이 없는 연결그래프
    - Kruskal, Prim 알고리즘은 모두 갈망 기법을 사용

* 갈망 기법(greedy method) : 단순한 조건에 확실한 해답에서부터 시작하여 한 단계씩 조건을 첨가하면서 연산을 반복함으로 최종 해법을 찾는 방법

 

  • 클루스컬 알고리즘
    - 간선의 길이에 의하여 간선들을 오름차순 정렬
    - 간선의 작은 순서로 선택하는데 단, 기존의 선택된 간선과 결합하여 사이클을 만들면 제외
    - 모든 정점이 연결되어 신장트리가 될 때까지 반복

 

  • 프림 알고리즘
    - 정점들을 연결된 부분과 연결되지 않은 부분의 두 영역으로 구분 (초기상태의 연결된 부분은 시작정점 하나)
    - 연결된 부분과 연결되지 않은 부분을 잇는 간선 중 최소의 간선을 택하고, 연결되지 않은 부분의 정점 중 이 간선에 근접한 정점을 연결한 부분으로 포함
    - 이 과정을 신장트리가 될 때까지 반복

 

* 클루스컬과 프림의 비교

- 클루스컬의 알고리즘은 간선 선택을 기반으로 하는 알고리즘인 반면, 프림의 알고리즘은 정점 선택을 기반으로 하는 알고리즘

- 클루스컬의 알고리즘은 이전 단계에서 만들어진 신장트리와는 상관없이 무조건 최소 간선만을 선택하는 방법인 반면, 프림의 알고리즘은 이전 단계에서 만들어진 신장트리를 확장하는 방식

- 간선 수가 적은 희소 그래프를 대상을 할 경우에는 클루스컬의 알고리즘이 적합하고, 간선 수가 많은 밀집 그래프의 경우에는 프림의 알고리즘이 적합하다고 할 수 있음

728x90