图的定义

图是由顶点的有穷非空集合和顶点之间边的集合组成。图可以用G = ( V , E )来表示，V表示顶点集合，E表示边集合，E中的边由A中的一对顶点连接而成。顶点总数为|V|，边的总数为|E|。

图的分类

稀疏图（sparse graph）：边数很少的图（|E|远小于|V|²）。

稠密图（dense graph）：边数较多的图（|E|接近|V|²）。

完全图（complete graph）：每对顶点之间都有唯一的边连接。

有向图（directed graph）：图点边限定为从一个顶点指向另一个顶点。

无向图（undirected graph）：图中的边没有方向。

标号图（labled graph）：图中各顶点均带有标号。

带权图（weighted graph）：边上标有权的图。（权（weight）：边可能附带的值。）

无环图（acyclic graph）：不带回路的图。

有向无环图（directed acyclic graph）：不带回路的有向图。

图的抽象数据类型（ADT）

基本操作
:
adjacent（x，y）：检测顶点x，y之间是否存在边；
neighbors（x）：列出所有存在到顶点x的顶点y;
add_vertex（x）：如果不存在则添加顶点x ;
remove_vertex（x）：如果存在顶点x则删除顶点x;
add_edge（x，y）：如果不存在从顶点x到顶点y的边则添加这条边;
remove_edge（x，y）：如果存在从顶点x到顶点y的边，则删除这条边;
get_vertex_value（x）：返回顶点x的值;
set_vertex_value（x，v）：给顶点x赋值为v;
get_edge_value（x，y）：返回边（x，y）的权;
set_edge_value（x，y，v）：将边（x，y）的权设置为v。

图的表示方法

一般稀疏图用邻接表来表示，稠密图用邻接矩阵来表示。

邻接矩阵

阶为n的图G的邻接矩阵A是n×n的二维矩阵。将G的顶点标签为v1，v2，…，vn。
若（vi，vj）∈E（G），Aij=1,否则Aij=0。
无向图的邻接矩阵是对称矩阵。

邻接表

如果是无向图，那么每条边由两个结点组成，分别代表边的两个端点；如果是有向图，那么每条边是一个结点对，分别代表边的始点和终点。

基本图算法

深度优先搜索

广度优先搜索

最小生成树

最短路径问题

Bellman-Ford算法（单源最短路径问题）

Dijkstra算法（单源最短路径问题）

Floyd-Warshall算法（所有结点对的最短路径问题）

参考文献

1. 数据结构与算法分析第三版（C++版）。第十一章，图。
2. 维基百科。Graph (abstract data type)，邻接矩阵。
3. 算法导论。图算法章节。