자료 구조론 9주차 - 그래프의 기초와 활용
그래프
직교 리스트
정의
희소 행렬의 표현을 위한 간단한 리스트 구조
사용시 임의의 점점 \(V_i\)에 대한 진출 차수와 진입 차수를 쉽게 산출이 가능함
리스트의 노드 형태
헤드 노드
- 4개의 필드를 포함하고 있음
필드
- Flag
- 헤드 노드, 간선 노드의 구분
- Index
- 희소 행렬의 행과 열 번호
- Down
- 동일 열에서 0이 아닌 다음 요소를 나타냄
- Right
- 동일 행에서 0이 아닌 다음 요소를 나타냄
간선 노드
- 5개의 노드를 포함하고 있음
필드
- Flag, Right, Down
- 행에서 0이 아닌 다음의 요소를 나타냄
- Tail
- 해당 간선의 꼬리
- Head
- 간선의 머리
인접 다중 리스트
무방향 그래프의 인접 리스트의 표현 단점
- 비효율적 메모리 활용
- 대안: 인접 다중 리스트
정의
- 여러 리스트들이 노드를 공유함
- 임의의 간선 \(e = (V_1, V_2)\)인 노드 구조의 형태임
- 5개의 필드를 포함하고 있음
1) mark
2) \(V_i\)
3) \(V_j\)
4) \(V_i\)에 대한 Link
5) \(V_j\)에 대한 Link
- 5개의 필드를 포함하고 있음
그래프의 순회
정의
무방향 그래프인 \(G=(V, E)\)와 \(V(G)\)에 있는 정점 V가 주어졌을떄 정점 V로부터 시작해 그래프의 모든 정점을 한 번씩만
방문해 모든 정점을 방문하는 것
종류
깊이 우선 탐색(DFS)
수행 방법
1) 시작 정점인 v를 결정 및 방문함
2) 시작 정점 V에 인접된 정점 중 방문하지 않은 정점 w를 선택해 DFS 탐색을 시작함
3) 더 이상 진행이 불가능할 경우, 마지막 갈림길로 돌아가 다시 진행함
4) 더 이상 방문할 노드가 존재하지 않을 경우, 탐색을 종료함
너비 우선 탐색(BFS)
수행 방법
- 출발점인 정점 v에서 출발함
- v에서 인접한 정점인 w를 모두 먼저 방문함
- w에 모두 방문한 후 w에 인접하고 방문하지 않은 모든 정점을 방문
- 더 이상 방문할 노드가 없을때까지 탐색을 진행함
신장 트리
신장 트리
정의
그래프 \(G\)의 간선의 일부나 전부와 모든 정점을 포함하는 트리1
그래프 \(G\)의 부분 그래프 \(G'\)
종류
깊이 우선 신장 트리(Depth First Spanning Tree)
- DFS에 의해 생성된 신장 트리
너비 우선 신장 트리(Breadth First Spanning Tree)
- BFS에 의해 생성된 신장 트리
응용
도로망 건설 계획
- 문제 정의: 최단거리로 모든 도시를 연결하기
- 각 간선들에 가중 값이나 거리 값을 부여함
- 문제의 해결을 위해서는 비용 최소화가 필요함
- 신장 트리의 비용
- 트리에 포함된 모든 간선의 가중 값의 합
최소 비용 신장 트리
정의
- 그래프 G의 각 간선에 +의 가중 값이 부여된 경우, 전체 하중 값의 합을 최소화 하는 신장 트리
종류
Prim Algorithsm
정의
- 최소 비용을 갖는 간선을 선택해 최소 비용 신장 트리인 T에 포함하는 것
- 트리 T에 포함된 정점들과 연결된 간선들 중 최소 비용을 갖는 간선을 트리에 T에 포함함
- 사이클이 생성되는 경우, 진행 상황을 버리고 방문하지 않은 간선 중 작은 것을 선택함
- 모든 정점을 방문하면 탐색이 중단됨
Kruskal Algorithsm
정의
- 간선들 중 가중치가 가장 낮은 최소 비용의 간선을 선택함
- 선택한 간선으로 인해 사이클이 발생할 경우, 제외함
- 위의 과정을 모든 정점이 연결 될때까지 반복함
Sollin Algorithsm
정의
- 그래프의 모든 정점들로 구성된 최소 비용의 간선을 하나씩 선택함
- 숲 내 트리에 대해 최소 비용의 간선을 1개씩 선택함
- 더 이상의 간선이 없거나, 완전한 트리가 생성 될 때까지 탐색을 계속함
Prim과 Kruskal 알고리즘과의 차이
- Prim과 Kruskal 알고리즘은 매 단계마다 하나의 간선을 선택해서 탐색함
- Sollin 알고리즘은 다수의 간선을 선택함
각 정점들간에 사이클이 존재하지 않음 ↩
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.