지난 학기들의 기록59 1 보호되어 있는 글 입니다. 2023. 2. 10. [강의노트] 최소신장트리 - 1 최소신장트리 - 1 가중그래프 간선에 무게를 가지는 그래프. 이미 배운 내용이라 익숙하다. 아래 가중그래프 예시를 보면, 각 지역(정점)을 잇는 간선의 무게는 여행거리(km)를 나타낸다. 신장트리 신장 부그래프를 다시 떠올려보면 , 모든 정점 + 부분간선의 그래프라고 외웠었다. 그 중에서 트리인 그래프를 우리는 신장트리라고 부른다. 다시 말하면, 신장트리(Spanning Tree)는 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 그림은 그래프 G의 노드 A,B,C를 모두 포함하지만 순환이 존재하지않는 그래프 G의 신장트리 3개를 보여주고 있다. 그럼 최소신장트리는 무엇일까? 최소신장트리는 신장트리 중에서 총 간선 무게의 합이 최소인 신장트리를 의미한다. 최소신장.. 2021. 11. 26. [강의노트] 방향그래프 - 2 방향 그래프 - 2 https://man-25-1.tistory.com/187 [강의노트] 방향 그래프 - 1 방향 그래프 - 1 지금까지 무방향 그래프의 구현과 수정, 그리고 순회알고리즘 DFS와 BFS에 대해서 다루어보았다. 이번에 배울 것은 간선에 방향성이 존재하는 방향그래프이다. 방향그래프 방향그 man-25-1.tistory.com 방향 그래프의 여러 개념들에 대해 배워보았고 이제는 구현방법에 대해 알아볼 차례이다. 동적프로그래밍 그전에 지난 포스팅에서 다루었던 동적 프로그래밍의 개념에 대해 한번 짚고 가면 동적프로그래밍은 언뜻 보기에 많은 시간이 소요될 것 같은 문제에 주로 적용된다. 적용 조건은 1. 부문제들이 단순해야한다 - 부문제들이 j, k, l, m 과 같은 몇 개의 변수로 정의 되어.. 2021. 11. 24. [강의노트] 방향그래프 - 1 방향 그래프 - 1 지금까지 무방향 그래프의 구현과 수정, 그리고 순회알고리즘 DFS와 BFS에 대해서 다루어보았다. 이번에 배울 것은 간선에 방향성이 존재하는 방향그래프이다. 방향그래프 방향그래프란 모든 간선이 방향간선인 그래프이다. 무방향 그래프에서 방향성만 추가된것이므로 개념은 어렵지않다.. 방향그래프에서 단순하다는 개념은 간선의 수를 m , 정점의 수를 n이라 할 때 m k -> j 의 경로를 구할 수 있게 되는 것이다. 방금 설명한 알고리즘에 대한 수도코드이다. 왼쪽의 설명을 참조하면 어렵지않게 이해할 수 있다. G_k-1 그래프의 정점 i,k 에 대한 경로와 k,j에 대한 경로를 확인하고, 만약 G_k에 vi,vj 경로가 없으면 삽입한다. 아까 설명한 1부터 k-1 까지 번호 매겨진 정점들만 .. 2021. 11. 17. 이전 1 2 3 4 ··· 15 다음
