자료구조 그래프 이론 조금 (무방향, 방향, 그래프 순회, 신장 트리 등)

그래프

 

 多 대 多 관계를 가지는 원소들을 표현하기 위한 자료구조

 

객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)가 있음

G = (V,E)

V는 정점들의 집합, E는 정점을 연결하는 간선들의 집합

 

 

그래프의 종류

 

무방향 그래프 : 간선의 방향이 없는 그래프 (v1,v2)로 표현 

(v1, v2) == (v2, v1) 같은 간선 

방향 그래프 : 간선이 방향을 가지고 있음 <v1, v2>로 표현 v1이 꼬리 v2를 머리라고 함 

<v1, v2> != <v2, v1> 다른 간선   

완전 그래프 : 각 정점에서 다른 모든 정점을 연결하여 가능한 최대의 간선 수를 가진 그래프

- 정점이 n개인 무방향 n(n-1)/2개

- 정점이 n개인 방향 n(n-1)개

부분 그래프 : 원래 그래프에서 일부 정점이나 간선을 제외하여 만든 그래프(부분집합)

가중치 그래프 : 가중치를 할당 

 

a와 b의 정점을 연결하는 간선 (a,b)가 있을 경우

: a,b는 인접되어 있음, 간선(a,b)는 a,b에게 부속되어 있음 

 

차수 : 정점에 부속되어 잇는 간선의 수

(트리에서는 자식노드의 개수를 말함)

방향그래프에서는 진입차수와 진출차수라는 개념이 있음 

 

경로 : 그래프에서 간선을 따라 갈 수 있는 길을 순서대로 나열한 것 

경로길이 : 경로를 구성하는 간선의 수

단순경로 : 중복X 

사이클 : 시작,마지막 같 

DAG : 방향그래프지만 싸이클 X

 

연결 그래프 : 다 연결되어 있음

단절 그래프 : 왕따가 존재함, 연결되지 않은 정점이 있음 

 

무방향 그래프의 인접 행렬

행과 열의 i의 합들은 정점 i의 차수와 같음

= 왜냐면 양쪽으로 진입 진출되기에 

방향에서는 행i에서의 1의 합이 정점i의 진출차수 / 열이면 진입차수

 

인접행렬표현의 단점

n개의 정점을 가지면 항상 nXn개의 메모리를 사용

메모리의 낭비 및 확장이 어려움 

 

인접리스트는 단순 연결 리스트

헤드포인터는 정점개수만큼 필요 -> 각각의 정점들이 시작점이 될 수 있기에 

 

그래프 순회 

: 하나의 정점에서 시작 -> 모든 정점 한번씩 방문 

깊이 우선 탐색 : 갈 수 있는 한 끝까지 깊이 들어간다 멀리멀리리ㅣ 멀리부터(스택사용)

너비 우선 탐색 : 인접한 정점들에 대해서 차례로 (큐사용)

 

 

신장트리

 

모든 정점이 연결 but 사이클이 없음

그래프 -> 트리 가능 /  트리 -> 그래프 불가능

경유지 -> 싸이클 : 무한루프가 일어남

 

최소 비용 신장 트리

: 가중치 합이 최소인 신장 트리

- 크루스칼의 알고리즘

- 프림의 알고리즘 이용

 

크루스칼은 내림차순이나 오름차순으로 정렬한 뒤 제거하면서~

프림은 간선을 정렬하지 않고 정점에서 시작해 트리를 확장하는 구조 (간선 검색 횟수 +, 정렬 안함)