Algorithm 썸네일형 리스트형 [그래프 알고리즘] 인접행렬과 그래프 (초보자용) 초보자를 위해서 써봅니다. (사실 저도 알고리즘 책 1권밖에 공부 안한 초보자입니다만 ^^;;) 이해에 관련된 민감한 오타등은 댓글 달아주심 고치도록 하겠습니다. 글자가 많아서 지루할수도 있지만 열심히 쓸테니 차근차근 읽어 주시면 감사하겠습니다. 문단은 글이 좀 길어질 경우 내용이 계속 이어지더라도 보기편하시라고 중간중간 띄어놓도록 하겠습니다. FOUNDATIONS of USING C++ PSEUDOCODE 저자 : Richard Neapolitan / Kumarss Naimipour 위의 책을 참고하였음을 밝힙니다. ^^ 사실 어떻게 보면 알고리즘 공부 전에 자료구조에서 그래프를 미리 접하는 경우가 있기 때문에... 알고리즘에서 굳이 인접행렬에 대해 설명 할 필요는 없습니다만... 앞에서와 같이 초보자.. Prim 알고리즘 발표자료 및 소스코드(matlab) Prim 알고리즘의 정의 최소비용 신장트리(MST) -주어진 그래프의 신장트리 중 전체 가중치의 합이 최소가 되는 것 우선순위 우선탐색(PFS)방식 -가설비용에 해당하는 간선에 가중치를 두고 가중치가 작은 것일수록 우선순위가 높다고 정의한 것 1. 시작할 정점을 임의로 선택한다. 2. 선택된 정점들에 부속된 간선들 중 가중치가 제일 작은 간선을 선택하여 최소 비용 신장 트리에 포함시킨다. 3. 선택된 간선에 인접한 정점들에 부속된 간선들에 대해서도 2를 반복한다. 4. 만약 사이클이 발생하면 선택한 간선은 제거하고 그 다음 가중치가 작은 간선이 있으면 선택하고 없으면 그 전에 방문한 정점에 연결된 간선에 대해 2를 반복한다. 5. 모든 정점이 연결되면 종료한다. % Program 'prim_1.m' (v.. 이전 1 다음
