Chapter 14. 최소 비용 신장 트리
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 사실 트리는 그래프의 한 유형입니다. 다음 그래프를 보겠습니다. 위 그래프의 정점 A로부터 D로 가는 경로들을 찾아보면 다음과 같이 찾을 수 있습니다. A - B - D A - C - D A - B - C - D A - C - B - D 이렇듯 두 개의 정점을 잇는 간선을 순서대로 나열한 것을 가리켜 '경로'라고 합니다. 그리고 위의 네 경로와 같이 동일한 간선을 중복하여 포함하지 않는 경로를 가리켜 '단순 경로'라고 합니다. 정점 A에서 D로 이르는, 단순 경로가 아닌 경로를 찾으면 다음과 같은 경로를 찾을 수 있습니다. A - ..
Chapter 14. 그래프의 탐색 (3)
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 이제 너비 우선 탐색 방법인 BFS를 구현해 볼 차례입니다. BFS의 구현을 위해서는 큐와 배열이 필요합니다. 배열은 DFS와 마찬가지로 각 정점에 방문한 정보를 기록하기 위해 사용됩니다. 그리고 DFS의 스택이 떠나온 정점을 저장하기 위해 사용됐다면, BFS에서 큐는 새로 방문한 정점들을 저장하기 위해 사용됩니다. DFS의 구현 방법을 설명할 때 사용한 것과 같은 그래프입니다. 이번에도 지율을 시작으로 모든 정점들을 방문할 것입니다. 지율이 시작 정점이므로 방문 기록을 남깁니다. 지율은 동수와 민석 모두에게 연락합니다. 다만, 동..
Chapter 14. 그래프의 탐색 (2)
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. DFS가 한 사람에게 연락을 취하는 방식이라면, BFS는 자신에게 연결된 모든 사람에게 연락을 취하는 방식입니다. 다음과 같은 그래프에서, 지율에게 비상 메시지가 도착했고, 지율로부터 시작해서 모두에게 비상 메시지를 전달해야 합니다. 이번에는 DFS와는 달리, 지율이 연락할 수 있는 모든 사람들에게 연락합니다. 그리고 동수와 민석도 각각 자신이 연락할 수 있는 모든 사람들에게 연락합니다. 다만 순서를 임의로 정했습니다. 동수와 민석이가 동시에 연락을 하지 않게 하기 위해 동수가 먼저 연락 가능한 모든 사람들에게 연락하고 이어서 민석..
연습문제 14. 01 DFS의 탐색 과정
위와 같은 비상 연락망을 대상으로 DFS의 탐색과정을 보이기 바랍니다. 이때 되돌아오는 과정까지 나열해야 하며 '수정'에서부터 시작하고, '수정'에서 끝나야 합니다. 그리고 연락할 대상이 둘 이상이라면 사전 편찬 순을 기준으로 연락 대상을 결정합니다. 예를 들어서 '동수'의 연락 대상은 '지민'과 '지율'입니다. 이때 '동수'는 지민에게 연락을 취합니다. 제가 작성한 답은 아래의 '더보기'를 클릭하여 확인할 수 있습니다. 더보기 수정, 민석, 지민, 동수, 지율, 동수, 지민, 민석, 정희, 민석, 수정
Chapter 14. 그래프의 탐색
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 그래프의 탐색은 그 어떤 자료구조보다도 복잡한 편입니다. 그래프는 정점의 구성뿐만 아니라 간선의 연결에도 규칙이 존재하지 않기 때문입니다. 그래서 그래프의 탐색을 위한, 다시 말해서 그래프의 모든 정점을 돌아다니기 위한 별도의 알고리즘 두 가지를 소개합니다. 깊이 우선 탐색 Depgh First Search(DFS) 너비 우선 탐색 Breadgh First Search(BFS) 우선은 깁이 우선 탐색의 방법을 먼저 설명하겠습니다. 아래의 그래프는 앞서 보였던 비상 연락망입니다. 현재 L 학생에게 비상 메시지가 전달되었습니다. 따라서..
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 그래프의 구현 관점에서 무방향 그래프와 방향 그래프의 유일한 차이점은 연결 리스트에 추가하는 노드의 수에 있기 때문에, 이 둘의 구현 방법에는 차이가 없다고 볼 수 있습니다. 굳이 따지자면 무방향 그래프를 구현할 때 연결 리스트에 추가해야 하는 노드의 수가 방향 그래프에 비해 두 배 많기 때문에 무방향 그래프의 구현이 좀 더 복잡하다고 할 수 있습니다. 그래서 무방향 그래프를 대상으로 구현해 보고자 합니다. 헤더 파일은 다음과 같습니다. //ALGraph.h //수정 날짜 : 2021.03.27 //작성자 : KOEY #ifndef..