자료구조 그래프 과제물

소개글

자료구조 그래프 과제물 및 시험 자료입니다.
중간고사, 기말고사 및 과제물 작성시 많은 도움이 될 것 입니다.

목차

1. 그래프 정의
2. 그래프의 종류
3. 그래프의 표현
4. 깊이 우선 탐색(DFS : Depth First Search)
5. 너비 우선 탐색(BFS : Breadth First Search)
6. 신장 트리(Spanning Tree)
7. Kruskal 알고리즘
8. Prim 알고리즘

본문내용

1. 그래프(Graph)
1. 정의
(1) 그래프는 연결되어 있는 객체간의 관계를 표현할 수 있는 자료구조다.
(2) 그래프는 정점(vertex)과 간선(node)들의 집합으로 구성된다.
(3) G=(V, E)로 표시한다. V(G)는 그래프 정점들의 집합을, E(G)는 그래프 G의 간선들의 집합을 의미한다.
(4) 정점의 차수는 그 정점에 부속된 간선들의 수이다.
(5) 이용분야는 위상순서, 최단경로, 작업 네트워크 등에 이용한다.

2. 무방향 그래프
(1) 무방향 그래프는 두 정점을 잇는 간선에 순서가 없다. 즉, 이다.
(2) 정점 에서 로 가는 방향이 표시되지 않는 그래프로, 양방향의 관계가 성립한다.
(3) 무방향 그래프에서 모든 정점의 차수의 합은 간선의 수에 2를 곱한 것과 같다.

(중략)

4. 깊이 우선 탐색(DFS : Depth First Search)
1. 정의
(1) 인접한 모든 정점들이 이미 방문한 정점 V인 경우는 가장 최근에 방문한 정점 중에서 방문하지 않은 정점 W
를 가진 정점을 선택하여 정점 W로부터 다시 깊이 우선 탐색을 시작한다.
(2) n개의 정점을 가진 무방향 그래프에서 깊이 우선 탐색 방법은 이진 트리에서 Preorder로 운행하는 방법을
일반화한 것이다.

(중략)

7. Kruskal 알고리즘
1. 최소 비용 간선 순으로 순서를 정한 뒤에 사이클을 형성하지 않으면 그 간선을 선택한다.
2. 각 단계의 결과는 하나 이상의 트리 즉, forest를 이룬다.

참고 자료

윤성우의 열혈 자료구조 ㅣ윤성우 저 ㅣ 오렌지미디어