Graph

Spanning Tree(신장트리)그래프 내의 모든 정점을 포함하는 트리 모든 정점들이 연결되어 있어야하고, 사이클을 포함해서는 안된다. 그래프의 최소 연결 부분 그래프이다. 최소연결 = 간선의 수가 가장 적다 그래프에 있는 n개의 정점(vertax)을 가지는 그래프의 최소 간선(edge) 수는 (n-1)개이고, (n-1)개의 간선으로 연결되 있으면 필연적으로 트리형태가 되므로 Spanning Tree가 되므로 즉, 그래프에서 일부 간선을 선택해서 만든 트리이다. 신장트리는 깊이 우선 탐색이나 너비 우선 탐색 을 이용하여 사용된 간선만 모으면 만들 수 있다. 하나의 그래프에 많은 신장 트리가 존재할 수 있다. [시작 정점을 바꾸어 가면서 깊이 우선 탐색을 하여 만든 신장 트리 중 일부] 깊이우선 탐색알고..

Graph(그래프) 그래프는 연결되어 있는 객체간의 관계를 표현할 수 있는 자료구조로 vertex(정점)와 edge(간선)의 집합으로 이루어진다. 그래프 용어 수학적으로는 G = (V,E)로 표시한다. V(G)는 그래프 G의 vertex들의 집합 E(G)는 그래프 G의 edge들의 집합 Vertex는 Node라고 불린다. Edge는 link라고 불린다. Vertex의 종류에 따라 무방향 그래프(Undirected Graph)와 방향 그래프(Directed Graph)로 구분된다. 무방향 그래프 : 'S---E' 화살표가 없는 선으로 이루어진 형태이다. 무방향 그래프는 간선이 방향성이 없는 그래프로 양방향으로 갈 수 있다. 정점의 차수(Degree)는 그 정점에 인접한 정점의 수를 말한다. 방향 그래프 :..