IT LAB

1. Kruskal AlgorithmMST 알고리즘 입니다.Union-Find, 정렬된 Edge set을 사용합니다. Greedy인접한 최소 비용의 간선을 선택하여 MST를 만듭니다. 2. 동작 순서1. 나무 초기화그래프의 각 꼭짓점을 각각 하나의 나무로 초기화합니다., 2. 정렬된 간선 집합 S 생성3. 숲 F 갱신S에서 가장 작은 가중치의 변을 뽑습니다.변의 꼭짓점이 이미 하나의 나무로 구성되어 있으면 버립니다. (사이클 방지)그 변에 연결된 두 나무를 하나의 나무로 만듭니다.전체적으로 하나의 숲을 만듭니다. S가 비어있지 않을 때까지 반복하여 모든 정점을 포함하는 최소 신장 트리를 만듭니다. 3. 예시  4. 구현static class Edge implements Comparable { fin..

1. Minimum spanning tree가중 그래프 + 무방향 그래프의 하위 트리 중,그래프의 모든 정점을 포함(spanning subgraph)하고, 사이클이 없으며, 가중치의 합이 최소인 하위트리를 말합니다. 2. Cut그래프의 정점들을 두 개의 분리된 집합으로 나누는 것을 의미합니다.각 집합은 비어있지 않습니다. Cut-Set컷을 통해 나뉜 두 집합의 정점들 사이를 잇는 모든 간선의 집합한 집합의 정점들과 다른 집합의 정점들 사이의 연결을 나타냅니다.Cut-Set에 속한 간선들을 제거하면, 그래프는 두 개의 연결되지 않은 부분 그래프로 나뉘게 됩니다. Cut Propertycut-set의 간선 중, 가중치가 가장 작은 간선들은 반드시 모든 MST에 포함됩니다.가장 가벼운 간선을 선택함으로써, 최..

난이도 : Gold 5 문제 링크 1. 문제 설명 요구사항 모든 사람들의 친구관계가 주어질 때, 아래와 같은 친구관계가 존재하는지 판별하라. 친구관계 A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다. 2. 내 풀이 5명의 사람이 연쇄적으로 친구인 관계 존재 여부 자료구조 (친구관계) 친구관계 : 양방향, 다대다, (친구 수)가변적 무방향 그래프 Vertex: 사람, Edge: 친구 인접 리스트 (메모리 관점에서) 자신의 친구들을 효율적으로 기억할 수 있음 코드 // 선언 private static List graph = new ArrayList(); // 초기화 for (int i = 0; i < nodeCnt; i++) { graph.add(new ArrayList()); ..