MST - 최소 신장 트리

MST Spanning Tree 그래프 내의 모든 정점을 포함하는 트리이다. Minimum Spanning Tree 그래프의 최소 연결 부분 그래프이다. n개의 정점을 가지고 있다면, 최소 간선의 수는 (n-1)개이다. Prim’s Algorithm 특징 정점 선택을 기반으로 하는 알고리즘 이전 단계에서 만들어진 신장 트리를 확장하는 방법 구현 배열 W : G의 인접 행렬 nearest[] : vi에 가장 가까운 정점 Y의 인덱스 distance[] : nearest[i] 의 정점과 v 사이의 가중치 구현 - java package prim; public class prim { static int inf = Integer.MAX_VALUE; public static class vertex{ int a,b..

• format_list_bulleted 알고리즘
• · 2023. 1. 27.
• textsms

String Matching [Navie, DFA, KMP]

String Matching Navie algorithm [설명] 텍스트의 시작부터 끝까지 패턴과 일치하는지 확인한다. [시간복잡도] $O(MN)$ [코드] static void search(String pat, String txt) { int l1 = pat.length(); int l2 = txt.length(); int i = 0, j = l2 - 1; for (i = 0, j = l2 - 1; j < l1;) { if (txt.equals(pat.substring(i, j + 1))) { System.out.println("Pattern found at index " + i); } i++; j++; } } DFA 알고리즘 [특징] Navie 알고리즘에서 각 숫자에 대한 표기를 하는 방식이다. 첫 ..

• format_list_bulleted 알고리즘
• · 2023. 1. 24.
• textsms