기술 블로그

[알고리즘] 최소 비용 신장 트리 ( MST )

입력 : n개의 도시, 도시와 도시를 연결하는 비용문제 : 최소의 비용으로 모든 도시들이 서로 연결되게 한다. 해가 유일하지는 않음예 : (b, c) 대신 (a, h)왜 트리라고 부르는가?싸이클이 없는 연결된 무방향 그래프를 트리라고 부른다.MST 문제의 답은 항상 트리가 됨 왜?Generic MST 알고리즘어떤 MST의 부분집합 A에 대해서 Au{(u,v)}도 역시 어떤 mst의 부분 집합이 될 경우 에지(u,v)는 A에 대해서 안전하다고 합니다. Generic MST 알고리즘 1. 처음에는 a =공집합으로 합니다.2. 집합 a에 대해서 안전한 에지를 하나 찾은 후 이것을 a에 더한다.에지의 개수가 n-1이 될 때까지 2번을 반복한다. 안전한 에지 찾기그래프의 정점들을 두 개의 집합 s와 v-s로 분할..

Directed Acyclic Graph - DAG는 방향 사이클(directed cycle)이 없는 방향 그래프 - 예 : 작업들의 우선순위 위상정렬DAG에서 노드들의 순서화 v1, v2, ... ,vn, 단, 모든 에지 (vi, vj)에 대해서 i위상정렬은 답이 유효하진 않습니다. indegree가 0인 것을 찾습니다. 이는 그 작업에 선행해야 하는 작업이 존재하지 않는 것입니다. a와 g는 아무때나 해도 상관없는 것입니다. 맨 처음에 a를 먼저 해도 된다는 것입니다. 그래프에서 indegree에서 0으로 하는 것이 제일 중요하구나 라는 것을 알아야 하며 두 개 이상 존재하면 그 중 하나를 출력합니다. A에서 나가는 엣지들은 이제 생각할 필요 없습니다. 남은 그래프에서 indegree가 0인 ..

Directed Acyclic Graph - DAG는 방향 사이클(directed cycle)이 없는 방향 그래프 - 예 : 작업들의 우선순위 위상정렬DAG에서 노드들의 순서화 v1, v2, ... ,vn, 단, 모든 에지 (vi, vj)에 대해서 i위상정렬은 답이 유효하진 않습니다. indegree가 0인 것을 찾습니다. 이는 그 작업에 선행해야 하는 작업이 존재하지 않는 것입니다. a와 g는 아무때나 해도 상관없는 것입니다. 맨 처음에 a를 먼저 해도 된다는 것입니다. 그래프에서 indegree에서 0으로 하는 것이 제일 중요하구나 라는 것을 알아야 하며 두 개 이상 존재하면 그 중 하나를 출력합니다. A에서 나가는 엣지들은 이제 생각할 필요 없습니다. 남은 그래프에서 indegree가 0인 ..

그래프의 개념과 표현그래프 G = (V,E)V : 노드(node) 혹은 정점(vertex)E : 노드쌍을 연결하는 엣지(Edge) 혹은 링크(link)개체(object)들 간의 이진관계를 표현n = |V|, m = |E|V={1,2,3,4,5,6,7,8}E={(1,2),(1,3),(2,3),...,(7,8)}n=8m=11방향 그래프와 가중치 그래프방향 그래프(Directed Graph) G=(V,E)에지(u,v)는 u로부터 v로의 방향을 가짐가중치 그래프 에지마다 가중치(weight)가 지정인접행렬adjacency matrix정점이 n개인 것을 n x n으로 표현한 것입니다. 1번부터 n번까지 모든 정점을 넘버링 한 것으로 I번째 행 J번째 열을 a_ ij라고 한다면 있으면 1 없으면 0으로 표시합니다...