[Data Structure] 10. 그래프

이 카테고리에 정리된 내용은 강의시간에 필기한 내용이 주를 이룹니다. 교수님께서 강의 하신 내용들 중에 핵심들과 부가적인 내용들을 요약하여 게시했습니다. 강의시간에 생능출판사의 C언어로 쉽게 풀어쓴 자료구조 책을 사용했기 때문에 정리하는 순서도 이 책의 순서에 따라 하기로 했습니다. 순전히 정리용이기 때문에 시험기간이나 복습용으로는 적절하지만 순수한 학습용으로는 적절하지 않을 수 있습니다.

목록보기

 

Data Structure

10.1 그래프

– 그래프(graph) : 연결되어 있는 객체간의 관계를 표현. 정점(vertex)과 간선(edge)의 집합. G = (V, E )로 표현.

– 오일러 경로 (Eulerian tour) : 그래프에 존재하는 모든 간선을 한번씩만 통과하면서 처음 정점으로 돌아오는 경로.어떤 지형에서 모든 다리를 한번씩만 건너서 출발했던 장소로 돌아올 수 있는가 라는 문제의 답 존재 여부를 증명. 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로가 존재.

– 무방향 그래프(undirected graph)  : 간선을 통해 양방향으로 갈 수 있음.

– 방향 그래프(directed graph) : 간선을 통해 한쪽 방향으로만 갈 수 있음.

– 가중치 그래프(weighted graph) : 네트워트(network)라고도 함. 간선에 비용이나 가중치가 할당된 그래프.

– 관절점 : 어떤 간선을 끊었을 때 그래프의 개수(연결 성분 connected component)가 늘어날 때의 그 지점.

– 부분그래프(subgraph) : 그래프 G를 구성하는 정점의 집합 V(G)와 간선의 집합 E(G)의 부분집합으로 이루어진 그래프.

– 인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점.

– 차수(degree) : 무방향 그래프에서 그 정점에 인접한 정점의 수(간선의 개수).

– 진입차수(in-degree) : 외부에서 오는 간선의 수

– 진출차수(out-degree) : 외부로 향하는 간선의 수

– 단순경로(simple path) : 경로중에서 반복되는 간선이 없는 경로.

– 사이클(cycle) : 단순경로의 시작정점과 종료정점이 동일한 경로.

– 완전그래프(complete graph) : 모든 정점이 서로 연결되어 있는 그래프.

 

10.3 그래프의 표현 방법

– 그래프 표현 방법 : 인접행렬(adjacency matrix) / 인접리스트(adjacency list)

– 인접행렬에 표현하는 방법 : M 이 인접행렬이라 할 때, 간선 (i, j)가 그래프에 존재한다면 M[i][j] = 1, 아니면 M[i][j] = 0으로 표시

– 밀집 그래프(dense graph) : 그래프에 간선이 많이 존재.

– 희소그래프(sparse graph) : 적은 숫자의 간선만을 가짐.

– 인접리스트에 표현하는 방법 : 각 연결리스트의 노드들은 인접 정점을 저장하고, 각 리스트의 헤드포인터들은 하나의 배열로 구성. 따라서 정점의 번호를 알면 이 번호를 배열의 인덱스로 하여 각 정점의 연결리스트에 쉽게 접근.

 

10.4 그래프의 탐색

– 그래프의 탐색 : 하나의 정점으로부터 차례로 모든 정점들을 한 번씩 방문.

  1. 인접 행렬로 표현
  2. visited array 만들기
  3. stack or queue사용

– 깊이우선 탐색(depth first search : DFS) : 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법. backtracking시에 stack을 사용해서 되돌아감.

– 너비우선탐색(breath first search : BFS) : 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문. queue를 통해 가까운 거리에 있는 정점을 차례로 저장한 후 꺼낼 수 있음.

 

10.5 연결성분

– 연결성분(connected component) : 최대로 연결된 부분 그래프. 깊이우선탐색이나 너비우선탐색을 이용하여 시작정점과 연결되어있는 모든 정점을 출력. 그 후 방문 안된 정점을 선택해서 다시 탐색을 실행하면 그 정점을 포함하는 연결성분을 찾을 수 있다.

 

10. 6 신장트리

– 신장트리(spanning tree) : 그래프 내의 모든 정점을 포함하는 트리. 모든 정점들이 연결되어있어야 하고, 사이클을 포함하지 않는다. n개의 정점을 정확히 (n-1)개의 간선으로 연결.

 

10.7 최소비용 신장트리

– 최소비용신장트리(minimum spanning tree : MST) : 모든 정점들을 가장 적은 수의 간선과 비용으로 연결.

– Kruskal’s MTS : 탐욕적인 방법(greedy method)을 이용. 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택.

  1. 먼저 간선들을 가중치의 오름차순으로 정렬. 가중치가 가장 낮은 간선을 선택.
  2. 다음에도 계속 가중치가 낮은 간선들을 차례로 선택하여 배열에 저장.
  3. 정점 n -1 까지 검사 후 종료.

– Prim’s MST : 인접한 정점들 중 최저 간선으로 연결된 정점을 선택하여 트리를 확장.

 

10.8 최단경로

– 최단경로 (shortest path) : 정점 i와 정점 j를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제.

– Dijkstra

  1. 집합 S를 시작 정점 v로부터의 최단경로가 이미 발견된 정점들의 집합이라고 하자.
  2. 시작정점에서 집합 s에 있는 정점만을 거쳐 다른 정점으로 가는 최단거리를 기록하는 배열을 distance라고 하자.
  3. 시작정점을 v라 하면 distance [v] = 0 이고 다른 정점에 대한 distance값은 시작정점과 해당 정점간의 가중치 값이 된다.
  4. 가중치는 보통 인접행렬에 저장되므로 인접 행렬을 weight 라 하면 distance [w] = weight[v][w] 가 된다.
  5. 정점 v에서 w로의 직접 간선이 없을 경우에는 무한대의 값을 저장한다.
  6. 알고리즘의 매 단계에서 최단거리가 발견되는 정점들이 s에 하나씩 추가된다.

– Floyd : 그래프에 존재하는 모든 정점 사이의 최단 경로를 한번에 모두 찾아주는 알고리즘. 2차원 배열을 이용하여 3중 반복.

  1. 인접행렬 weight : i == j이면 weight[i][j] = 0으로 하고 만약 두개의 정점 i, j 사이에 간선이 존재하지 않으면 무한대로 둔다.
  2. 정점 i, j 사이에 간선이 존재하면 weight[i][j]는 해당 간선의 가중치가 된다.

– 선행 : 어떤 방향그래프에서 간선 <u,v>가 있다면 정점 u는 정점 v를 선행한다고 말한다.

– 위상 정렬(topological sort) : 방향그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것.

– 위상 순서(topological order) : 위상정렬 알고리즘이 진행되는 과정에서 선택되는 정점의 순서.

 

 

목록보기