Robert Sedgewick , Kevin Wayne (2011), Algorithms 4th edition, Pearson.

알고리즘 구현할 때 참고하기 좋은 책을 소개합니다.

Algorithms라는 빨간 표지를 한 책입니다.

Graph를 자바로 구현하려면 어떻게 해야 하나 찾아보다 찾은 책입니다.

이 책의 큰 장점은 책의 내용과 자바(java) 소스를 자신의 온라인 웹 사이트에 공개해두었다는 겁니다.

그래프 라이브러리 찾기 전에 이걸 먼저 봤습니다.

그래프 자료 구조는 두 가지를 쓸 수 있습니다.

모든 데이터를 행렬(matrix) 형태로 저장하는 방법과 인접 리스트(adjacency list)에 넣어두고 쓰는 방법인데요.

예를 들면, 아래 그림 같은 다섯 개의 노드로 된 그래프는 다음과 같이 나타낼 수 있습니다.

행렬로 표현하면 아래와 같습니다.

인접 리스트로 표현하면 아래와 같습니다.

이런 것들이 자바로 구현되어 있습니다.

그래프 공부하다보면 또 구현해야할 게 이것 저것 많은데요. 공부를 위해서 직접 구현해보면 멋있겠지만, 그 때는 전에 포스트한 자바용 라이브러리 JGraphT를 추천합니다(

2016/04/29 - [노트정리/그래프 이론 graph theory] - JGraphT. 그래프(graph 또는 네트워크 network) 관련한 알고리즘을 자바에서 구현할 때 편리한 라이브러리)

아래는 책이 담고 있는 내용을 저자의 웹사이트에서 긁어왔습니다. 본문은 링크를 아래 챕터 번호를 클릭해서 링크를 따라가면 보실 수 있습니다.

• Chapter 1: Fundamentals introduces a scientific and engineering basis for comparing algorithms and making predictions. It also includes our programming model.
• Chapter 2: Sorting considers several classic sorting algorithms, including insertion sort, mergesort, and quicksort. It also includes a binary heap implementation of a priority queue.
• Chapter 3: Searching describes several classic symbol table implementations, including binary search trees, red-black trees, and hash tables.
• Chapter 4: Graphs surveys the most important graph processing problems, including depth-first search, breadth-first search, minimum spanning trees, and shortest paths.
• Chapter 5: Strings investigates specialized algorithms for string processing, including radix sorting, substring search, tries, regular expressions, and data compression.
• Chapter 6: Context highlights connections to systems programming, scientific computing, commercial applications, operations research, and intractability.