[자료구조#14, 15] 그래프

개념 및 용어

관계를 그래프로 추상화하여 다룰 수 있음

정의 : 정점을 포함하는 집합 V와 두 정점의 쌍으로 구성되는 간선을 포함하는 집합 E의 순서쌍으로 정의

간선은 두 정점 쌍으로 나타냄

두 정점이 서로 인접한다 : 연결하는 간선이 존재

독립 정점

널 그래프

경로 : 간선의 열 (연결되어있다)

경로의 길이 : 경로에 있는 간선의 수

 

 

가중 그래프 : 간선이 가중치를 갖는 그래프

완전 그래프 : 모든 저점들이 간선으로 서로 연결될 그래프

무방향 그래프의 간선 개수

 

루프 : 길이가 1개인 경로

사이클 : 처음과 끝이 같은 경우

무사이클 그래프(트리) : 사이크리 없는 그래프

 

추상 자료형

그래프 표현 방법

그래프 탐색

그래프 순회

깊이 우선 탐색 : 깊이 있게 들어가는 것

인접한 모든 정점들이 이미 방문한 지점에 있는 것인 경우 정점 중에서, 방문하지 않은 정점 𝑤𝑤 를 가진 정점을 선택하여 정점 𝑤𝑤 로부터 다시 깊이 우선 탐색을 시작

 

너비 우선 탐색

트리 : 사이클이 없는 단순 그래프

 

크루스컬 알고리즘 : 무조건 최소 비용인 간선을 선택 하고 사이클을 형성 X 그 간선을 선택

솔린 알고리즘 : 간선이 하나도 없는 그래프의 모든 정점들로 구성된 숲에서 시작함
➲단계가 거듭되면서 숲 내의 트리들이 최소 비용을 갖는 간선으로 연결