本文为图算法的先导篇，将会介绍和图相关的概念以及代码实现。

一、图的定义

图 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 中边的条数。

线性表可以是空表，树可以是孔数，但图不能是空图（图的顶点集不能为空，边集可以为空）


以下是图的基本概念和术语：

  1. 有向图：

    $G_1=(V_1,E_1)$

    $V_1={1,2,3}$

    $E_1={<1,2>,<2,1>,<2,3>}$

    image-20210208145422908

  2. 无向图：

    $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)}$

    image-20210208145655017

  3. 简单图：

    若一个图满足： (I) 不存咋重复边；(II) 不存在从顶点到自身的边；

    则称为简单图。（一般数据结构中只讨论简单图）

  4. 多重图：

    若图 G 中某两点之间的边多于一条，又允许顶点通过一条边和自己关联，则 G 为多重图。（多重图的定义和简单图相对）

  5. 简单完全图：

    对于无向图，任意两个顶点之间都存在边（共 $n(n-1)/2$ 条）

    对于有向图，任意两个顶点之间同时存在出边和入边（共 $n(n-1)$ 条）

  6. 子图：

    边集和顶点集都为原图的子集，同时需要格外注意，新的顶点集和边集必须可以构成图

  7. 连通、连通图、连通分量：

    在无向图中，若从顶点 v 到顶点 w 有路径存在，则称 v 和 w 是连通的。

    若图 G 中任意两个顶点都是连通的，则称图 G 为连通图，否则为非连通图。

    无向图中极大连通子图称为连通分量。（极大要求该连通子图需要包含原图所有的边）

  8. 强连通图、强连通分量：

    在有向图中，若两不同顶点之间互相都有路径，则称这两个顶点是强连通的。

    若图中的任意一对顶点都是强连通的，则将图称为强连通分量。

  9. 生成树、生成森林：

    对于生成树而言，如果砍去它的一条边，图将从连通图变成非连通图；如果加上一条边则会形成一个回路。

    在非连通图中，连通分量的生成树构成了非连通图的生成森林。

二、图的存储：

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
3
4
5
6
7
8
#define MaxVertexNum 100
typedef char VertexTtype;
typedef int EdgeType;
typedef struct {
    VertextType Vex[MaxVertexNum];  // 顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum];  // 邻接矩阵（边表）
    int vexnum,arcnum;   // 弧当前的顶点数和弧数
} MGraph;

2. 邻接表法：

当一个图的边集较少时（即顶点间的关系不复杂），使用邻接矩阵方法会浪费大量的存储空间，此时，图的邻接表法结合了顺序存储和链式存储的方法，大大减少了空间开销。

所谓邻接表，是指对图 G 中的每个顶点建立一个单链表，链表存储依附于该结点的其他结点（这个单链表就成为顶点的边表）。各边表的头指针和顶点数据采用顺序存储（称为顶点表）。

image-20210208163013602

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

image-20210208163013602

使用 c/c++ 语言描述为：

1
2
3
4
5
6
7
8
9
10
11
12
13
#define MaxVertexNum 100
typedef struct ArcNode {  //// 边表节点
    int adjvex;             // 该弧指向的顶点
    struct ArcNode *next;   // 指向下一条弧的指针
}ArcNode;
typedef struct VNode {    //// 顶点表节点
    VertexType data;        // 顶点信息
    ArcNode *first;         // 指向第一条依附于该顶点的弧指针
}VNode,AdjList[MaxVertexNum];
typedef struct {
    VAdjList vertices;   // 邻接表
    int vexnum,arcnum;   // 图的顶点数和弧数
} MGraph;

三、图的基本操作

  1. Adjacent(G, x, y)：判断是否存在边 <x, y> 或 (x, y)
  2. Neighbors(G, x)：列出图 G 中与节点 x 邻接的边
  3. InsertVertex(G, x)：在图 G 中插入顶点 x
  4. DeleteVertex(G, x)：在图 G 中删除顶点 x
  5. AddEdge(G, x, y)：若无向边 (x, y) 或有向边 <x, y> 不存在，则向图 G 中添加该边
  6. RemoveEdge(G, x, y)：若无向边 (x, y) 或有向边 <x, y> 存在，则在图 G 中删除该边
  7. FirstNeighbor(G, x)：求图 G 中顶点 x 的第一个邻接点，若有则返回顶点号。
  8. NextNeighbor(G, x, y)：假设图 G 中顶点 y 是顶点 x 的一个邻接点，返回除 y 外顶点 x 的下一个邻接顶点号
  9. GetEdgeValue(G, x, y)：获取图 G 中边 (x, y) 或 <x, y> 对应的权值
  10. SetEdgeValue(G, x, y, v)：设置图 G 中边 (x, y) 或 <x, y> 对应的权值为 v

（由于操作的实现基于数据结构，而实现图的数据结构复杂多样，此处不提供代码）