최소 신장 트리 그래프 G=(V,E)의 신장 트리는 정점 집합 V를 그대로 두고 간선을 |V|-1개만 남겨 트리가 되도록 만든 것입니다. 임의의 그래프로부터 만들 수 있는 신장 트리는 매우 다양합니다. 너비 우선 트리와 깊이 우선 트리도 신장 트리입니다. 간선들이 가중치를 갖는 그래프에서 간선 가중치의 합이 가장 작은 트리를 최소 신장 트리라고 합니다. 밑은 최소신장 트리 종류중 하나인 프림 알고리즘입니다. 1. Prim's 알고리즘 Prim's 알고리즘은 최소 우선순위 큐에서 가중치가 가장 작은 정점을 선택한 후, 그 정점의 인접한 정점들에 대해 key 값과 연결된 가중치 값을 비교하여 key값을 갱신할 지 말지 결정합니다. 초기 그래프입니다. 모든 정점들의 key 값은 inf가 할당되어 있습니다. 그..

위상 정렬(Topological Sort)이란 어떤 일을 하는 순서를 찾는 알고리즘이다. 즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것 위상 정렬(Topological Sort)의 특징 하나의 방향 그래프에는 여러 위상 정렬이 가능하다. 위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서(Topological Order)라 한다. 위상 정렬의 과정에서 그래프에 남아 있는 정점 중에 진입 차수가 0인 정점이 없다면, 위상 정렬 알고리즘은 중단되고 이 러한 그래프로 표현된 문제는 실행이 불가능한 문제가 된다. 간선 (i, j)가 존재하면 정렬 결과에서 정점 i는 반드시 정점 j보다 앞에 위치해야 한다. 위상 정렬(Topological Sort)을 이용한 ..

그래프 탐색이란 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것 Ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 너비 우선 탐색(BFS, Breadth-First Search) 너비 우선 탐색이란 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다. 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다. Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 ..

그래프의 개념 그래프는 현상이나 사물을 정점과 간선으로 표현하는 것이다. 정점(Vertex)은 대상이나 개체를 나타내고 간선(Edge)은 이들 간의 관계를 나타낸다. 예를 들어, 사람 간의 친밀도를 나타내고 싶다고 하자. 각 사람을 하나씩의 정점으로 표시한다. 서로 친말한 사람 간에는 간선을 둔다. 그러면 과 같은 그래프가 된다. 각 간선은 간선으로 연결된 두 사람이 친밀함을 나타낸다. 간선은 두 도시를 연결하는 도로의 존재 여부, 두 집안 간의 혼인 여부 등을 나타낼 수 있다. 그림 2는 그림 1을 조금 변형한 것이다. 그림 1이 사람 간의 친물도 존재 여부만 표시하는 데 비해 그림 2는 친밀도의 크기까지 표시한다. 즉, 간선에 가중치를 주어 친밀감의 정도를 보여준다. 이런 가중치는 도시 간의 거리, ..