数据结构 408-6-1&2 - 数据结构 - 计算机科学 | Flüstern = Whispering's Blog = 无需过去，无关未来，只有现在

# 图的基本概念

# 图的定义

图 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)\vert u\in V,v\in V$ }，用 | E | 表示图 G 中边的条数

注意：线性表可以是空表，树可以是空树，但图不可以是空，即 V 一定是非空集

# 无向图

若 E 是无向边 (简称边) 的有限集合，则图 G 为无向图。边是顶点的无序对，记为 (v,w) 或 (w,v)，因为 (v,w)=(w,v)，其中 v、w 是顶点。可以说顶点 w 和顶点 v 互为邻接点。边 (v,w) 依附于顶点 v 和 w，或者说边 (v,w) 和顶点 v、w 相关联

# 有向图

若 E 是有向边 (简称弧) 的有限集合，则图 G 为有向图。边是顶点的有序对，记为 < v,w>，其中 v 称为弧尾，w 称为弧头，<v,w > 称为顶点 v 到顶点 w 的弧，也称 v 邻接到 w，或 w 邻接自 v。 $<v,w>\neq <w,v>$

# 简单图

不存在重复边
不存在顶点到自身的边

# 多重图

图 G 中某两个节点之间边数多于 1 条，有允许顶点通过同一条边和自己关联，则 G 为多重图

# 顶点的度、入度、出度

对于无向图：

顶点 v 的度是指依附于该顶点的边的条数，记为 TD (v)

对于有向图：

入度是以顶点 v 为终点的有向边的数目，记为 ID (v)
出度是以顶点 v 为起点的有向边的数目，记为 OD (v)
顶点 v 的度等于其入度和出度的和，即 TD (v)=ID (v)+OD (v)

在具有 n 个顶点、e 条边的有向图中， $\sum\limits_{i=1}^nID(v_i)=\sum\limits_{i=1}^nOD(v_i)=e$

# 顶点 - 顶点的关系描述

路径 —— 顶点 $v_p$ 到顶点 $v_q$ 之间的一条路径是指顶点序列， $v_p,v_{i_1},v_{i_2},...,v_{i_m},v_q$

回路 —— 第一个顶点和最后一个顶点相同的路径称为回路或环

简单路径 —— 在路径序列中，顶点不重复出现的路径称为简单路径

简单回路 —— 除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路

路径长度 —— 路径上边的数目

点到点的距离 —— 从顶点 u 出发顶点顶点 v 的最短路径若存在，则此路径的长度称为从 u 到 v 的距离，若从 u 到 v 根本不存在路径，则记该距离为无穷

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

有向图中，若从顶点 v 到顶点 w 和从顶点 w 到顶点 v 之间都有路径，则称这两个顶点是强联通的

# 连通图、强联通图

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

若图中任何一对顶点都是强联通的，则称此图为强联通图

常见考点：

对于 n 个顶点的无向图 G

若 G 是连通图，则最少有 n-1 条边
若 G 是非连通图，则最多可能有 $C_{n-1}^2$ 条边
若 G 是强联通图，则最少有 n 条边 (形成回路)

# 子图、连通分量、强联通分量、生成树、生成森林

设有两个图 G=V,E} 和(\prime$={$V^\prime,E^\prime$)$G，若 $V^\prime$ 是 V 的子集，且 $E^\prime$ 是 E 的子集，则称 $G^\prime$ 是 G 的子图

若有满足 $V(G^\prime)=V(G)$ 的子图 $G^\prime$ ，则称其为 G 的生成子图

无向图中极大连通子图称为连通分量（子图必须连通，且包含尽可能多的顶点和边）

有向图中的极大强联通子图称为有向图的强联通分量 (子图必须强联通，同时保留尽可能多的边)

连通图的生成树是包含图中全部顶点的一个极小连通子图 (边尽可能少，但要保持连通)

若图中顶点数为 n，则它的生成树含有 n-1 条边，对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路

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

# 边的权、带权图 / 网

边的权 —— 在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。

带权图 / 网 —— 边上带有权值的图称为带权图，也称为网

带权路径程度 —— 当图是带权图时，一条路径上所有的权值之和，称为该路径的带权路径长度

# 几种特殊形态的图

无向完全图 —— 无向图中任意两个顶点之间都存在边

若无向图的顶点数 | V|=n，则 $\vert E\vert\in[0,C_n^2]=[0,\frac{n(n-1)}{2}]$

有向完全图 —— 有向图中任意两个顶点之间都存在方向相反的两条弧

若有向图的顶点数 | V|=n，则 $\vert E\vert\in[0,2C_n^2]=[0,n(n-1)]$

边数很少的图称为稀疏图，反之称为稠密图（没有绝对的界限，一般来说 | E|<|V|log|V | 时，可以将 G 视为稀疏图）

树 —— 不存在回路，且连通的无向图

常见考点：n 个顶点的图，若 | E|>n-1，则一定有回路

有向树 —— 一个顶点的入度为 0，其余顶点的入度均为 1 的有向图，称为有向树

# 图的存储

# 邻接矩阵法

#define MaxVertexNum 100                    //顶点数目的最大值
typedef struct{
    char Vex[MaxVertexNum];                 //顶点表
    int Edge[MaxVertexNum][MaxVertexNum];   //邻接矩阵，边表
    int vexnum,arcnum;                      //图当前顶点数和边数/弧数
} MGraph;

顶点中可以存更复杂的信息，可以用 bool 型或枚举型变量表示边

结点数为 n 的图 G=(V,E) 的邻接矩阵 A 是 nxn 的，将 G 的顶点编号为 $v_1,v_2,...,v_n$ ，则

$A[i][j]=\begin{cases}1&if(v_i,v_j)or<v_i,v_j>\in E(G)\\0&if(v_i,v_j)or<v_i,v_j>\notin E(G)\end{cases}$

无向图：

第 i 个结点的度 = 第 i 行 (或第 i 列) 的非零元素个数

有向图：

第 i 个结点的出度 = 第 i 行非零元素个数

第 i 个结点的入度 = 第 i 列的非零元素个数

第 i 个结点的度 = 第 i 行、第 i 列的非零元素个数之和

邻接矩阵求顶点度 / 出度 / 入度的时间复杂度为 O (|V|)

# 邻接矩阵法存储带权图 (网)：

#define MaxVertexNum 100                           //顶点数目的最大值
#define INFINITY 0x7f7f7f7f7f                      //宏定义常量无穷
typedef char VertexType;
typedef int EdgeType;
typedef struct{
    VertexType Vex[MaxVertexNum];                  //顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum];     //边的权
    int vexnum,arcnum;                             //图当前顶点数和边数/弧数
} MGraph;

用一个极大值表示无穷

# 邻接矩阵的性能分析：

空间复杂度： $O(\vert V\vert^2)$ —— 只和顶点相关，和实际的边数无关

适合用于存储稠密图

无向图的邻接矩阵是对称矩阵，可以压缩矩阵（只存储上三角区 / 下三角区）

# 邻接矩阵性质

设图 G 的邻接矩阵为 A (矩阵元素为 0/1，则 $A^n$ 的元素 $A^n[i][j]$ 等于由顶点 i 到顶点 j 的长度为 m 的路径的数目

# 邻接表法 (顺序 + 链式存储)

//顶点
typedef struct VNode{
    VertexType data; //顶点信息
    ArcNode *first;  //第一条边/弧
}VNode,AdjList[MaxVertexNum];
//用邻接表存储的图
typedef struct {
    AdjList vertices;
    int vexnum,arcnum;
} ALGraph;
//边/弧
typedef struct ArcNode{
    int adjvex;           //边/弧指向哪个节点
    struct ArcNode *next; //指向下一条弧的指针
    //InfoType info;      //边权值
}ArcNode;

无向图：边节点的数量是 2|E|，整体空间复杂度为 O (|V|+2|E|)

有向图：边界点的数量是 | E|，整体空间复杂度为 O (|V|+|E|)

图的邻接表表示方式并不唯一

# 邻接表与邻接矩阵对比

	邻接表	邻接矩阵
空间复杂度	无向图 O (\|V\|+2\|E\|)，有向图 O (\|V\|+\|E\|)	O(\|V\|*\|V\|)
适合用于	存储稀疏图	存储稠密图
表示方式	不唯一	唯一
计算度 / 出度 / 入度	计算有向图的度、入度不方便，其余很方便	必须遍历对应行或列
找相邻的边	找到有向图的入边不方便，其余很方便	必须遍历对应行或列

# 十字链表法

只能存储有向图

十字链表法存储有向图：

弧节点：tailvex+headvex+info+hlink+tlink

tailvex：弧尾顶点编号
headvex：弧头顶点编号
info：权值
hlink：弧头相同的下一条弧
tlink：弧尾相同的下一条弧

顶点节点 (用数组顺序存储)：data+firstin+firstout

data：数据域
fisrtin：该顶点作为弧头的第一条弧
firstout：该顶点作为弧尾的第一条弧

# 十字链表法性能分析

空间复杂度：O (|V|+|E|)

# 邻接多重表

只能存储无向图

邻接多重表存储无向图

边结点：i+j+info+iLink+jLink

边的两个顶点编号 i，j
info：权值
iLink：依附于顶点 i 的下一条边
jLink：依附于顶点 j 的下一条边

顶点结点：data+firstedge

data：数据域
firstedge：与该顶点相连的第一条边