1 개요 #

그래프 데이타 구조와 알고리즘 분야는 다른 컨테이너 분야보다 몇몇 부분에 있어서는 더 복잡합니다. STL에서 사용하는 추상 반복자(abstract iterator) 인터페이스는 그래프 알고리즘이 그래프를 횡단(traverse)하는데 필요한 수많은 방법을 포괄하기에는 충분하지 않습니다. Instead, we formulate an abstract interface that serves the same purpose for graphs that iterators do for basic containers (though iterators still play a large role). 그림 1은 STL과 BGL간의 유사성을 나타내고 있습니다.

http://www.boost.org/libs/graph/doc/figs/analogy.gif

그림 1: STL와 BGL간의 유사성

The graph abstraction consists of a set of vertices (or nodes), and a set of edges (or arcs) that connect the vertices. Figure 2 depicts a directed graph with five vertices (labeled 0 through 4) and 11 edges. The edges leaving a vertex are called the out-edges of the vertex. The edges {(0,1),(0,2),(0,3),(0,4)} are all out-edges of vertex 0. The edges entering a vertex are called the in-edges of the vertex. The edges {(0,4),(2,4),(3,4)} are all in-edges of vertex 4.

http://www.boost.org/libs/graph/doc/figs/quick_start.gif

그림 2: 유향그래프(directed graph)의 예

In the following sections we will use the BGL to construct this example graph and manipulate it in various ways. The complete source code for this example can be found in examples/quick_tour.cpp. Each of the following sections discusses a "slice" of this example file. Excerpts from the output of the example program will also be listed.