비선형 자료구조 - 그래프

N 대 M 대응 구조로 노드와 선분으로 구성되어있다.

트리와 다른점은 서로 사이클이 형성되는 경우를 그래프라고 표현한다.

주로 최단 거리 탐색, 전자 회로 분석, 통계학과 같은 분야에서 사용된다.

 

 

비방향 그래프(Undirected Graph)와 방향 그래프(Directed Graph)

정점과 간선의 연결관계에 있어서 방향성이 없는 그래프를 Undirected Graph 라 하고, 간선에 방향성이 포함되어 있는

그래프를 Directed Graph 라고 한다.

 

 

그래프 탐색

너비 우선 탐색 (BFS) :

시작점에서 시작하여, 연결된 정점 끝까지 내려간다. 끝나는 지점을 만나게 되면 다시 되돌아와 

그 옆부터 끝까지 검색한다. 밑 까지 검색하다 다시 되돌아가야 하니 stack과 같은 자료구조를 사용하면 된다.

 

깊이 우선 탐색 (DFS) : 

그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 모든 정점으로 나아간다.

큐를 사용하여 지나간 정점들을 기억하여 탐색하는 방법이다.

 

 

 

 

최소 비용 신장 트리 (Minimum Spanning Tree)

 

Kruskal 알고리즘 : 

간선 비용이 가장 적은 순서대로 연결하는 방식이며, 시작 정점과 끝 정점이 같지 않도록 연결한다.

 

Prim 알고리즘 :

간선의 연결이 하나의 트리에서 추가되어가는 방식으로, 연결할 수 있는 간선 중에 비용이 가장 적은걸 추가시킨다.

트리가 확장되어 가는 형태이며 kruskal처럼 시작 정점과 끝 정점이 같지 않도록 연결한다.