C++ Boost 

adjacency_matrix<Directed, VertexProperty,
                 EdgeProperty, GraphProperty,
                 Allocator>

该adjacency_matrix类使用传统的邻接矩阵存储格式实现 BGL 图接口。对于具有 V 个顶点的图，使用 V x V 矩阵，其中每个元素 aij 是一个布尔标志，指示是否存在从顶点 i 到顶点 j 的边。图 1 显示了一个图的邻接矩阵表示。

图 1： 有向图的邻接矩阵表示。

与邻接列表相比，这种矩阵格式的优点是边插入和删除是常数时间。但也存在几个缺点。首先是使用的内存量是 O(V2) 而不是 O(V + E)（其中 E 是边的数量）。其次，遍历每个顶点的所有出边的操作（例如广度优先搜索）运行时间为 O(V2) 而不是邻接列表的 O(V + E) 时间。简而言之，最好使用adjacency_matrix对于稠密图（其中 E 接近 V2），最好使用 adjacency_list 对于稀疏图（其中 E 远小于 V2）。该adjacency_matrix类扩展了传统的数据结构，允许使用 adjacency_list 支持的相同属性模板参数将对象附加到顶点和边。这些可以是捆绑属性或标准（向后兼容）内部属性。所有属性值的类型必须是可复制构造、可赋值和默认可构造的。在无向图的情况下，adjacency_matrix. 类不使用完整的 V x V 矩阵，而是使用下三角矩阵（对角线及以下），因为无向图的矩阵是对称的。这会将存储空间减少到 (V2)/2。图 2 显示了一个无向图的邻接矩阵表示。

图 2： 无向图的邻接矩阵表示。

示例

创建 图 1 的图。
  enum { A, B, C, D, E, F, N };
  const char* name = "ABCDEF";

  typedef boost::adjacency_matrix<boost::directedS> Graph;
  Graph g(N);
  add_edge(B, C, g);
  add_edge(B, F, g);
  add_edge(C, A, g);
  add_edge(C, C, g);
  add_edge(D, E, g);
  add_edge(E, D, g);
  add_edge(F, A, g);

  std::cout << "vertex set: ";
  boost::print_vertices(g, name);
  std::cout << std::endl;

  std::cout << "edge set: ";
  boost::print_edges(g, name);
  std::cout << std::endl;

  std::cout << "out-edges: " << std::endl;
  boost::print_graph(g, name);
  std::cout << std::endl;
输出为
  vertex set: A B C D E F

  edge set: (B,C) (B,F) (C,A) (C,C) (D,E) (E,D) (F,A)

  out-edges:
  A -->
  B --> C F
  C --> A C
  D --> E
  E --> D
  F --> A
创建 图 2 的图。
  enum { A, B, C, D, E, F, N };
  const char* name = "ABCDEF";

  typedef boost::adjacency_matrix<boost::undirectedS> UGraph;
  UGraph ug(N);
  add_edge(B, C, ug);
  add_edge(B, F, ug);
  add_edge(C, A, ug);
  add_edge(D, E, ug);
  add_edge(F, A, ug);

  std::cout << "vertex set: ";
  boost::print_vertices(ug, name);
  std::cout << std::endl;

  std::cout << "edge set: ";
  boost::print_edges(ug, name);
  std::cout << std::endl;

  std::cout << "incident edges: " << std::endl;
  boost::print_graph(ug, name);
  std::cout << std::endl;
输出为
  vertex set: A B C D E F

  edge set: (C,A) (C,B) (E,D) (F,A) (F,B)

  incident edges:
  A <--> C F
  B <--> C F
  C <--> A B
  D <--> E
  E <--> D
  F <--> A B

定义位置

boost/graph/adjacency_matrix.hpp

模板参数

参数描述默认值
Directed 一个选择器，用于选择图是有向的还是无向的。选项有directedS和undirectedS. directedS
VertexProperty 用于指定内部属性存储。 no_property
EdgeProperty 用于指定内部属性存储。 no_property
GraphProperty 用于指定图对象的属性存储。 no_property

模型

VertexAndEdgeListGraph, Incidence Graph, Bidirectional Graph, AdjacencyMatrix, MutablePropertyGraph, CopyConstructible, 和 Assignable。

关联类型

graph_traits<adjacency_matrix>::vertex_descriptor

与以下项关联的顶点描述符的类型adjacency_matrix.
（Graph 要求。）
graph_traits<adjacency_matrix>::edge_descriptor

与以下项关联的边描述符的类型adjacency_matrix.
（Graph 要求。）
graph_traits<adjacency_matrix>::vertex_iterator

由以下项返回的迭代器的类型vertices()。顶点迭代器模型 RandomAccessIterator。
（VertexListGraph 要求。）
graph_traits<adjacency_matrix>::edge_iterator

由以下项返回的迭代器的类型edges()。此迭代器模型 MultiPassInputIterator。
（EdgeListGraph 要求。）
graph_traits<adjacency_matrix>::out_edge_iterator

由以下项返回的迭代器的类型out_edges()。此迭代器模型 MultiPassInputIterator。
（IncidenceGraph 要求。）
graph_traits<adjacency_matrix>::in_edge_iterator

由以下项返回的迭代器的类型in_edges()。此迭代器模型 MultiPassInputIterator。
（BidirectionalGraph 要求。）
graph_traits<adjacency_matrix>::adjacency_iterator

由以下项返回的迭代器的类型adjacent_vertices()。此迭代器模型与出边迭代器相同的概念。
（AdjacencyGraph 要求。）
graph_traits<adjacency_matrix>::directed_category

提供关于图是否是有向图的信息（directed_tag）或无向图（undirected_tag).
（Graph 要求。）
graph_traits<adjacency_matrix>::edge_parallel_category

邻接矩阵不允许插入平行边，因此此类型始终为disallow_parallel_edge_tag.
（Graph 要求。）
graph_traits<adjacency_matrix>::vertices_size_type

用于处理图中顶点数量的类型。
（VertexListGraph 要求。）
graph_traits<adjacency_matrix>::edges_size_type

用于处理图中边数量的类型。
（EdgeListGraph 要求。）
graph_traits<adjacency_matrix>::degree_size_type

用于处理顶点的出边数量的类型。
（IncidenceGraph 要求。）
property_map<adjacency_matrix, PropertyTag>::type
property_map<adjacency_matrix, PropertyTag>::const_type

图中顶点或边属性的映射类型。具体属性由PropertyTag模板参数指定，并且必须与VertexProperty或EdgeProperty图中指定的属性之一匹配。
（PropertyGraph 要求。）

成员函数

adjacency_matrix(vertices_size_type n,
                 const GraphProperty& p = GraphProperty())
创建一个具有n个顶点和零条边的图对象。
（MutableGraph 要求。）
template <typename EdgeIterator>
adjacency_matrix(EdgeIterator first,
                 EdgeIterator last,
                 vertices_size_type n,
                 const GraphProperty& p = GraphProperty())
创建一个具有n个顶点，边由范围给定的边列表指定[first, last)。的value类型EdgeIterator必须是std::pair，其中pair中的类型是整数类型。整数将对应于顶点，并且它们都必须在[0, n).
的范围内（IteratorConstructibleGraph 要求。）
template <typename EdgeIterator, typename EdgePropertyIterator>
adjacency_matrix(EdgeIterator first, EdgeIterator last,
                 EdgePropertyIterator ep_iter,
                 vertices_size_type n,
                 const GraphProperty& p = GraphProperty())
创建一个具有n个顶点，边由范围给定的边列表指定[first, last)。的value类型EdgeIterator必须是std::pair，其中pair中的类型是整数类型。整数将对应于顶点，并且它们都必须在[0, n)。该value_type的ep_iter应该是EdgeProperty.

非成员函数

std::pair<vertex_iterator, vertex_iterator>
vertices(const adjacency_matrix& g)
返回一个迭代器范围，提供对图的顶点集的访问g.
（VertexListGraph 要求。）
std::pair<edge_iterator, edge_iterator>
edges(const adjacency_matrix& g);
返回一个迭代器范围，提供对图的边集的访问g.
（EdgeListGraph 要求。）
std::pair<adjacency_iterator, adjacency_iterator>
adjacent_vertices(vertex_descriptor v, const adjacency_matrix& g)
返回一个迭代器范围，提供对顶点v在图中的邻接顶点的访问g.
（AdjacencyGraph 要求。）
std::pair<out_edge_iterator, out_edge_iterator>
out_edges(vertex_descriptor v, const adjacency_matrix& g)
返回一个迭代器范围，提供对顶点v在图中的邻接顶点的访问g的出边的访问。如果图是无向图，则此迭代器范围提供对顶点上的所有关联边的访问v.
（IncidenceGraph 要求。）
vertex_descriptor
source(edge_descriptor e, const adjacency_matrix& g)
返回边e.
（IncidenceGraph 要求。）
vertex_descriptor
target(edge_descriptor e, const adjacency_matrix& g)
返回边e.
（IncidenceGraph 要求。）
degree_size_type
out_degree(vertex_descriptor u, const adjacency_matrix& g)
返回离开顶点u.
（IncidenceGraph 要求。）
std::pair<in_edge_iterator, in_edge_iterator>
in_edges(vertex_descriptor v, const adjacency_matrix& g)
返回一个迭代器范围，提供对顶点v在图中的邻接顶点的访问g的出边的访问。如果图是无向图，则此迭代器范围提供对顶点上的所有关联边的访问v.
（BidirectionalGraph 要求。）
degree_size_type
in_degree(vertex_descriptor u, const adjacency_matrix& g)
返回进入顶点u.
（BidirectionalGraph 要求。）
vertices_size_type num_vertices(const adjacency_matrix& g)
返回图中的顶点数g.
（VertexListGraph 要求。）
edges_size_type num_edges(const adjacency_matrix& g)
返回图中的边数g.
（EdgeListGraph 要求。）
vertex_descriptor vertex(vertices_size_type n, const adjacency_matrix& g)
返回图中顶点列表中的第 n 个顶点。
std::pair<edge_descriptor, bool>
edge(vertex_descriptor u, vertex_descriptor v,
     const adjacency_matrix& g)
返回连接顶点u到顶点v在图中的邻接顶点的访问g.
的边（AdjacencyMatrix 要求。）
std::pair<edge_descriptor, bool>
add_edge(vertex_descriptor u, vertex_descriptor v,
         adjacency_matrix& g)
添加边(u,v)到图中，并返回新边的边描述符。如果边已在图中，则不会添加重复项，并且bool标志将为false。此操作不会使图的任何迭代器或描述符失效。
（MutableGraph 要求。）
std::pair<edge_descriptor, bool>
add_edge(vertex_descriptor u, vertex_descriptor v,
         const EdgeProperty& p,
         adjacency_matrix& g)
添加边(u,v)到图中，并将p作为边内部属性存储的值附加。另请参阅之前的add_edge()成员函数以获取更多详细信息。
void remove_edge(vertex_descriptor u, vertex_descriptor v,
                 adjacency_matrix& g)
从图中移除边(u,v)。
（MutableGraph 要求。）
void remove_edge(edge_descriptor e, adjacency_matrix& g)
从图中移除边e从图中移除。这等效于调用remove_edge(source(e, g), target(e, g), g).
（MutableGraph 要求。）
void clear_vertex(vertex_descriptor u, adjacency_matrix& g)
移除所有到顶点和来自顶点的边u。顶点仍然出现在图的顶点集中。
（MutableGraph 要求。）
template <typename Property>
property_map<adjacency_matrix, Property>::type
get(Property, adjacency_matrix& g)

template <typename Property>
property_map<adjacency_matrix, Property>::const_type
get(Property, const adjacency_matrix& g)
返回由Property。该Property指定的顶点属性的属性映射对象，必须与图的VertexProperty模板参数中指定的属性之一匹配。
（PropertyGraph 要求。）
template <typename Property, typename X>
typename property_traits<
  typename property_map<adjacency_matrix, Property>::const_type
>::value_type
get(Property, const adjacency_matrix& g, X x)
这将返回x的属性值，它既可以是顶点描述符也可以是边描述符。
（PropertyGraph 要求。）
template <typename Property, typename X, typename Value>
void
put(Property, const adjacency_matrix& g, X x, const Value& value)
这将属性值设置为x到value. x，它既可以是顶点描述符也可以是边描述符。Value必须可转换为typename property_traits<property_map<adjacency_matrix, Property>::type>::value_type.
（PropertyGraph 要求。）
template <typename GraphProperty, typename GraphProperty>
typename property_value<GraphProperty, GraphProperty>::type&
get_property(adjacency_matrix& g, GraphProperty)
返回由GraphProperty指定的属性，该属性附加到图对象g。该property_value特性类在boost/pending/property.hpp. 
template <typename GraphProperty, typename GraphProperty>
const typename property_value<GraphProperty, GraphProperty>::type&
get_property(const adjacency_matrix& g, GraphProperty)
返回由GraphProperty指定的属性，该属性附加到图对象g。该property_value特性类在boost/pending/property.hpp.