[최소 비용 신장 트리에 들어가기에 앞서] 책에서도 나온 말이지만 그래프로 시작했는데 결국 또 트리 이야기가 나왔다. 그런데 사실 트리 역시 그래프의 한 유형이다. 이는 곧 이어서 보게 될 '사이클이 없는 그래프'를 보면 바로 이해가 될 것이다. [사이클을 형성하지 않는 그래프 == 신장 트리] 이 그래프에서 정점 B에서 D로 가는 방법을 나열해보면 다음과 같다. B-A-D / B-C-D / B-A-C-D / B-C-A-D 이처럼 두 개의 정점을 잇는 간선을 순서대로 나열한 것을 가리켜 '경로(Path)'라고 한다. 그리고 동일한 간선을 중복하여 포함하지 않는 경로를 '단순 경로(Simple Path)'라고 한다. B-A-C-B-A-D 와 같은 경로는 B-A를 잇는 간선이 두 번 포함되므로 단순 경로가 ..

[그래프의 탐색에 들어가기에 앞서] 연결 리스트나 배열과 같은 선형 자료구조에서는 탐색해야 할 방향이 정해져있다. 그래서 탐색과 조회를 진행하는 것이 어렵지 않았다. 트리와 같은 비선형 자료구조는 노드의 연결 방향이 일정하지 않기 때문에 탐색을 진행하는 것이 비교적 어렵다. 그렇지만 이진 탐색 트리는 노드가 연결되는 규칙이 있었기 때문에 비교적 간단한 편이었다. 말 그대로 '탐색'을 고려해서 만들어진 트리이기 때문이다. 그런데 그래프에서의 탐색은 어떻게 해야할까? 지금까지 학습했던 자료구조들 중에서 탐색 과정이 꽤 복잡한 편이다. 적어도 연결 리스트나 배열같은 선형 자료구조도 그렇고, 이진 탐색 트리도 그랬듯 '틀'이 있었다. 정형화된 구조가 있었기 때문에 탐색을 어떻게 할 것인가를 정의할 수 있었지만 ..

[그래프에 들어가기에 앞서] 그래프 역시 자료구조이며, 비선형 자료구조에 해당한다. 그리고 트리 때와도 마찬가지로 데이터의 저장보다는 '표현'을 하는데 중점적이다. 실제로 그래프라는 자료구조를 배우게 되면 그래프보다는 그래프와 관련된 알고리즘들을 더 많이 보게 된다. 이는 자료구조에서 저장소의 측면보다는 하나의 '표현 방법'으로 더 많이 사용된다는 것을 의미한다고 볼 수 있다. 그래서 '그래프 자료구조'라는 표현보다는 '그래프 알고리즘'이라는 용어가 더 많이 쓰이게 되고 실제로도 그렇다. [그래프의 이해와 종류] 위의 문제는 '쾨니히스베르크의 다리 문제'라는 유명한 문제다. 그리고 이 문제를 풀기 위해서 오일러라는 수학자에 의해 '그래프 이론'이 사용되었다고 한다. 위의 그림을 그래프로 만들면 다음과 같..