本文为图算法的先导篇,将会介绍和图相关的概念以及代码实现。
一、图的定义
图 G 由顶点集 V 和边集 E 组成,记作 $G=(V,E)$。
$V(G)$ 表示图 G 中顶点的有限非空集合
E(G) 表示图 G 中顶点之间的边关系集合。
$V={v_1,v_2,…,v_n}$ ,用 |V| 表示图 G 中顶点的个数,也称图 G 的阶。
$E={(u,v)|u\in V,v\in V}$,用 |E| 表示图 G 中边的条数。
线性表可以是空表,树可以是孔数,但图不能是空图(图的顶点集不能为空,边集可以为空)
以下是图的基本概念和术语:
有向图:
$G_1=(V_1,E_1)$
$V_1={1,2,3}$
$E_1={<1,2>,<2,1>,<2,3>}$
无向图:
$G_2=(V_2,E_2)$
$V_2={1,2,3}$
$E_2={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}$
简单图:
若一个图满足: (I) 不存咋重复边;(II) 不存在从顶点到自身的边;
则称为简单图。(一般数据结构中只讨论简单图)
多重图:
若图 G 中某两点之间的边多于一条,又允许顶点通过一条边和自己关联,则 G 为多重图。(多重图的定义和简单图相对)
简单完全图:
对于无向图,任意两个顶点之间都存在边(共 $n(n-1)/2$ 条)
对于有向图,任意两个顶点之间同时存在出边和入边(共 $n(n-1)$ 条)
子图:
边集和顶点集都为原图的子集,同时需要格外注意,新的顶点集和边集必须可以构成图
连通、连通图、连通分量:
在无向图中,若从顶点 v 到顶点 w 有路径存在,则称 v 和 w 是连通的。
若图 G 中任意两个顶点都是连通的,则称图 G 为连通图,否则为非连通图。
无向图中极大连通子图称为连通分量。(极大要求该连通子图需要包含原图所有的边)
强连通图、强连通分量:
在有向图中,若两不同顶点之间互相都有路径,则称这两个顶点是强连通的。
若图中的任意一对顶点都是强连通的,则将图称为强连通分量。
生成树、生成森林:
对于生成树而言,如果砍去它的一条边,图将从连通图变成非连通图;如果加上一条边则会形成一个回路。
在非连通图中,连通分量的生成树构成了非连通图的生成森林。
二、图的存储:
1. 邻接矩阵法:
所谓邻接矩阵,就是用一个一维数组存储图中顶点信息,用一个二维数组存储图中边的信息(各顶点之间的邻接关系)。其中,存储顶点之间邻接关系的二维数组称为邻接矩阵。
$A[i][j]=\begin{cases} 1& \text{若 $(v_i,v_j)$ 或 $<v_i,v_j>$ 是 E(G) 中的边} \\0& \text{若 $(v_i,v_j)$ 或 $<v_i,v_j>$ 不是 E(G) 中的边} \end{cases}$
对于带权图来说,若顶点 $v_i$ 和 $v_j$ 之间有边相连,则邻接矩阵中应存放边对应的权值。
$A[i][j]=\begin{cases} w_{ij}& \text{若 $(v_i,v_j)$ 或 $<v_i,v_j>$ 是 E(G) 中的边} \\0\ 或\ \infty& \text{若 $(v_i,v_j)$ 或 $<v_i,v_j>$ 不是 E(G) 中的边} \end{cases}$
使用 c/c++ 语言描述为:
1 |
|
2. 邻接表法:
当一个图的边集较少时(即顶点间的关系不复杂),使用邻接矩阵方法会浪费大量的存储空间,此时,图的邻接表法结合了顺序存储和链式存储的方法,大大减少了空间开销。
所谓邻接表,是指对图 G 中的每个顶点建立一个单链表,链表存储依附于该结点的其他结点(这个单链表就成为顶点的边表)。各边表的头指针和顶点数据采用顺序存储(称为顶点表)。

以下是为读者更为清晰地理解邻接表法存储而举出的例子:

使用 c/c++ 语言描述为:
1 |
|
三、图的基本操作
- Adjacent(G, x, y):判断是否存在边 <x, y> 或 (x, y)
- Neighbors(G, x):列出图 G 中与节点 x 邻接的边
- InsertVertex(G, x):在图 G 中插入顶点 x
- DeleteVertex(G, x):在图 G 中删除顶点 x
- AddEdge(G, x, y):若无向边 (x, y) 或有向边 <x, y> 不存在,则向图 G 中添加该边
- RemoveEdge(G, x, y):若无向边 (x, y) 或有向边 <x, y> 存在,则在图 G 中删除该边
- FirstNeighbor(G, x):求图 G 中顶点 x 的第一个邻接点,若有则返回顶点号。
- NextNeighbor(G, x, y):假设图 G 中顶点 y 是顶点 x 的一个邻接点,返回除 y 外顶点 x 的下一个邻接顶点号
- GetEdgeValue(G, x, y):获取图 G 中边 (x, y) 或 <x, y> 对应的权值
- SetEdgeValue(G, x, y, v):设置图 G 中边 (x, y) 或 <x, y> 对应的权值为 v
(由于操作的实现基于数据结构,而实现图的数据结构复杂多样,此处不提供代码)