1. 무향 그래프에서 사이클 union find 알고리즘을 이용해서 쉽게 판단할 수 있다 https://deepdata.tistory.com/432 union find 알고리즘 활용 - 사이클을 판별하는 방법 -1. 사이클 판별 서로소 집합 알고리즘은 무방향 그래프에서 사이클을 판별할 때 사용할 수 있다. 방향 그래프에서 사이클 여부는 DFS로 확인할 수 있다고 한다 핵심 원리는 union 연산이 그래프에deepdata.tistory.com 간선을 확인하면서, 간선을 연결하는 두 노드의 대표자가 서로 같다면 사이클이 발생하는것이고, 서로 다르다면 union을 수행하면 된다 2. 유향 그래프에서 사이클 한 노드에서 출발했다가, 다른 노드들을 거쳐 이동하다보니 출발 노드로 돌아오면 사이클이 존재한다고 한..
1. 방향 비순환 그래프(Directed acyclic graph) 사이클이 존재하지 않는 방향 그래프 정점 u에서 출발했을때, u로 돌아오는 방법이 없다. 다음과 같은 그래프는 방향 비순환 그래프(DAG)이다. 2. 한 정점에서 다른 정점까지 가장 긴 경로의 길이 정점 v에 대하여 DP[v]를 v에서 출발할때 도달할 수 있는 가장 긴 경로의 길이라고 정의한다면... 다음과 같이 v에서 c1,c2,c3,...로 갈 수 있을텐데, c1,c2,c3,...에서 출발하여 도달할 수 있는 가장 긴 경로의 길이 DP[c1],DP[c2],...가 이미 구해져있다면... DP[v] = max(wi + DP[ci])으로 구할 수 있을 것이다. 다이나믹 프로그래밍은 이미 해결한 작은 문제를 이용해서 더 큰 문제를 해결하는..
1. 신장트리(spanning tree) n개의 정점으로 이루어진 "무방향 그래프"에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 하나의 그래프가 있을때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 이때, 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이다. 그래서 이러한 그래프를 신장 트리라고 부른다. 위와 같은 그래프에서 신장 트리는 여러개 찾을 수 있다. 예를 들어 아래와 같은 그래프는 하나의 신장 트리이다. 하지만 다음 그림과 같은 그래프들은 신장 트리가 아니다. 구체적으로 다음은 노드 1을 포함하고 있지 않다 다음은 노드 4-6-7에서 사이클이 발생하므로 신장트리가 아니다. 2. 최소 신장 트리(Minimum spanning tree)..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
