최소 신장 트리(Minimum Spanning Tree) 란?그래프에서 모든 정점에 대해 최소한의 연결만을 남긴 그래프이다. 즉, 간선의 가중치 합이 가장 작은 트리를 뜻한다.사이클이 존재하지 않아야 한다.  최소 신장 트리를 찾는 알고리즘으로는 다음과 같이 두 가지가 있다.1. Prim 알고리즘2. Kruskal 알고리즘  Prim 알고리즘프림 알고리즘은 아래의 방법을 반복한다. 단, 아래 과정을 반복하는 과정에서 사이클이 형성되지 않아야 한다.1. 임의의 정점을 선택하여 하나의 정점을 가지는 최초의 트리를 구성한다. 2. 트리에 포함된 정점과 트리에 포함되지 않은 정점 간의 간선 중, 가장 가중치가 적은 간선을 선택하여 트리에 추가한다.3. 모든 정점이 트리에 포함될 때까지 2를 반복한다. 예시1) ..

DFS 알고리즘이란?DFS(Depth-First Search)란 깊이 우선 탐색이라고도 불리며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.  DFS 알고리즘 작동 과정1. 정점 i를 방문한다.2. 정점 i에 인접한 정점 중에서 아직 방문하지 않은 정점이 있으면, 이 정점들을 모두 스택에 저장한다.3. 스택에서 정점을 삭제하여 새로운 i를 설정하고, 단계 (1)을 수행한다.4. 스택이 공백이 되면 연산을 종료한다 배열 visited[n]을 이용하여, 정점의 방문 여부를 표시한다- visited[i] = True : 방문하였음- visited[i] = False: 방문하지 않음  BFS 알고리즘 작동 예시 0. visited배열 전부 False로 초기화 1. stack에 시작 원소 삽입    2..

BFS 알고리즘이란?BFS(Breadth-First Search)란 너비 우선 탐색이라고도 불리며 그래프에서 시작 노드에 인접한 노드부터 탐색하는 알고리즘이다. 주로 그래프에서 모든 간선의 비용이 동일한 조건에서 최단 거리를 구하는 문제를 효과적으로 해결할 수 있다. BFS 알고리즘 작동 과정1. 정점 i를 방문한다.2. 정점 i에 인접한 정점 중에서 아직 방문하지 않은 정점이 있으면, 이 정점들을 모두 큐에 저장한다.3. 큐에서 정점을 삭제하여 새로운 i를 설정하고, 단계 (1)을 수행한다.4. 큐가 공백이 되면 연산을 종료한다 배열 visited[n]을 이용하여, 정점의 방문 여부를 표시한다- visited[i] = True : 방문하였음- visited[i] = False: 방문하지 않음 그림 1 ..

그래프그래프는 원소를 정점과 간선으로 표현한 것이다. 두 정점이 간선으로 연결되어 있으면 인접하다고 한다. 그래프는 크게 2가지로 표현할 수 있다.  1. 인접 행렬(Adjacency Matrix)인접 행렬이란, 그래프의 연결 관계를 행렬로 표현하여 이차원 배열로 나타내는 방식이다. adg[i][j] = 1 (노드 i에서 노드 j로 가는 간선이 존재할 경우)adg[i][j] = 0 (노드 i에서 노드 j로 가는 간선이 존재하지 않을 경우)  1. 무향그래프  만약 표현하고자 하는 그래프가 방향이 없는 무향 그래프일 경우, 노드 i에서 노드 j로 가는 길이 존재하면, 노드 j에서 노드 i로 가는 길 또한 존재한다. 이러한 특성으로 인해 인접 행렬을 구현하게 되면, 대각 성분을 기준으로 대칭인 성질을 가지게..