본문 바로가기
728x90
반응형

개발 일기58

알고리즘 - 단절점 (Articulation Points / Cut Vertices) 알고리즘 - 단절점 (Articulation Points / Cut Vertices) 1. 단절점이란? 무향 연결 그래프 G에서 하나의 정점과 연결된 간선들을 제거했을 때 두 개의 연결 그래프로 나뉘어 진다면 해당 정점은 단절점이다. 예를 들어 5에 있는 간선들을 모두 제거해도 그래프가 두 개로 나누어지지 않기 때문에 5는 단절점이 아니다. 그러나 4에 있는 간선들을 모두 제거할 경우 두 개의 연결 그래프로 나뉘어지기 때문에 단절점이다. 2. 단절점 찾기 - 무향 연결 그래프 G에서 어떤 정점 A에 연결된 정점들에 대해서 우회 경로 (정점 A를 거치지 않는 경로)가 없는 경우가 존재한다면 A는 단절점이다. orderV : 정점 V의 방문순서 lowV : 정점 V의 low (V 이후에 방문하는 정점들 중 .. 2021. 2. 3.
알고리즘 - 최소 공통 조상 (LCA, Lowest Common Ancestor) 알고리즘 - 최소 공통 조상 (LCA, Lowest Common Ancestor) 정점 A와 정점 B가 각각 자신을 포함하여 조상을 따라 거슬러 올라 갈 때 처음 공통으로 만나게 되는 정점이다. 정점 A혹은 A의 조상이면서 정점 B 혹은 B의 조상인 정점들 중 가장 깊은 정점이다. 8과 9의 공통 조상들은 1, 2, 4 / 8과 9의 최소 공통 조상은 4 3과 6의 공통 조상들은 1, 3 / 3과 6의 최소 공통 조상은 3 8과 5의 공통 조상들은 1, 2 / 8과 5의 최소 공통 조상은 2 [ 최소 공통 조상 구하기 ] - 최상위 조상 정점을 시작으로 DFS 혹은 BFS를 수행하여 각 정점의 깊이와 부모 정점을 저장한다. - 정점의 부모를 따라 하나씩 올라가 LCA를 찾는다. 시간복잡도 : 트리의 깊이.. 2021. 2. 3.
알고리즘 - 크루스칼 알고리즘(Kruskal's Algorithm), 프림 알고리즘(Prim's Algorithm) 알고리즘 - 크루스칼 알고리즘(Kruskal's Algorithm), 프림 알고리즘(Prim's Algorithm) jina-developer.tistory.com/114 자료구조 - 최소 신장 트리 (MST, Minimum Spanning Tree) [개요] 1. 트리란? 1) 무향 그래프 G가 순환이 없는 그래프이면 G는 숲이다. 2) 무향 그래프 G가 순환이 없는 연결 그래프이면 G는 트리이다. - G는 순환이 없고, 단순 그래프에서 간선을 추가할 경우 jina-developer.tistory.com 1. 크루스칼 알고리즘(Kruskal's Algorithm) 1) 순서 모든 간선들의 가중치를 오름차 순으로 정렬 가중치가 가장 작은 간선을 선택 위에서 선택한 간선이 연결하려는 2개의 노드가 서로 연.. 2021. 2. 2.
자료구조 - 최소 신장 트리 (MST, Minimum Spanning Tree) [개요] 1. 트리란? 1) 무향 그래프 G가 순환이 없는 그래프이면 G는 숲이다. 2) 무향 그래프 G가 순환이 없는 연결 그래프이면 G는 트리이다. - G는 순환이 없고, 단순 그래프에서 간선을 추가할 경우 순환이 생긴다. - G는 연결 그래프이고, 어떤 간선을 제거하면 연결그래프가 아니다. - G의 어떤 두 정점에 대해서 단순 경로가 하나 존재한다. 2. 신장 트리 (Spanning Tree) - 무향 연결 그래프 G의 부분그래프이고 G의 모든 정점을 포함하는 트리(Tree)인 그래프 1) 깊이 우선 신장 트리 (DFS Spanning Tree) 무향 연결 그래프 G에서 깊이 우선 탐색(DFS)으로 탐색하면서 생성된 신장 트리 (Spanning Tree) 2) 너비 우선 신장 트리 (BFS Span.. 2021. 2. 2.
알고리즘 - 위상정렬 (Topological Sort) 알고리즘 - 위상정렬 (Topological Sort) DAG(비순환 방향 그래프)에서 그래프의 방향성을 거스르지 않고 정점들을 나열하는 알고리즘으로 위상정렬은 각 정점을 우선순위에 따라 배치한다. 일반적으로 결과는 유일하지 않다. jina-developer.tistory.com/112 자료구조 - DAG (Directed Acyclic Graph) 1. Directed Acyclic Graph란? DAG란 순환을 가지지 않는 방향그래프를 말한다. 일반적으로 우선순위를 가진 일련의 작업들은 DAG구조를 가진다. - 선행자(predecessor), 후행자(successor) : DAG에서 어떤 정점 v.. jina-developer.tistory.com 각 노드들의 진입 차수 계산 진입 차수가 0인 노드들.. 2021. 2. 2.
자료구조 - 비순환 방향 그래프 (DAG, Directed Acyclic Graph) 1. 비순환 방향 그래프란? 비순환 방향 그래프(DAG, Directed Acyclic Graph)란 순환을 가지지 않는 방향그래프를 말한다. 일반적으로 우선순위를 가진 일련의 작업들은 DAG구조를 가진다. 1) 선행자(predecessor), 후행자(successor) DAG에서 어떤 정점 vi, vj에 대해서 vi에서 vj로의 경로가 존재하면, vi, vj의 선행자(predecessor), vj는 vi의 후행자(successor)라고 한다. 2) 즉각 선행자(immediate predecessor), 즉각 후행자(immediate successor) DAG에서 어떤 정점 vi, vj에 대해서 vi에서 vj로의 간선이 존재하면, vi를 vj의 즉각 선행자(immediate predecessor), vj.. 2021. 2. 2.
728x90
반응형

티스토리툴바