数据结构之图

图的定义和术语

图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关；而在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。由此，图的应用极为广泛，特别是近年来的迅速发展，已渗入到诸如语言学，逻辑学，物理，化学，电讯工程，计算机科学以及数学的其他分支中去。

在图中的数据元素通常称作顶点，$V$是顶点的有穷非空集合；$VR$是两个顶点之间的关系的集合。若$\in VR$，则$$表示从v到w的一条弧，且称$v$为弧尾或初始点，称$w$为弧头或终端点，此时的图称为有向图。若$\in VR$必有$\in VR$，即$VR$是对称的，则以无序对$(v,w)$代替这两个有序对，表示$v$和$w$​之间的一条边，此时的图称为无向图。

我们用n表示图中顶点数目，用e表示边或弧的数目。在下面的讨论中，我们不考虑顶点到其自身的弧或边，即若$ \in VR$​，则$v_i\neq v_j$​，那么，对于无向图，e的取值范围是0到$\frac 12n(n-1)$​。有$\frac 12n(n-1)$​​条边的无向图称为完全图。对于有向图，e的取值范围是0到$n(n-1)$​。具有$n(n-1)$条弧的有向图称为有向完全图。有很少条边或弧的图称为稀疏图，反之称为稠密图。

有时图的边或弧具有与它相关的数，这种与图的边或弧相关的数叫做权。这些权可以表示从一个顶点到另一个顶点的距离或者耗费。这种带权的图通常称为网。

假设有两个图$G=(V,{E})$和$G’=(V’{E’})$，如果$V’\in V$且$E’\in E$,则称$G’$为$G$的子图。

对于无向图$G+(V,{E})$​,如果边$(v,v’)\in E$​，则称顶点$v$​和$v’$​互为邻接点，即$v$​和$v’$​相邻接。边$(v,v’)$​依附于顶点v和v‘，或者说$(v,v’)$​和顶点v相关联。顶点$v$​的度是和$v$​相关联的边的数目，记为$TD(V)$​。对于有向图$G=(V,{A})$​，如果弧$\in A,$​则称顶点$v$​邻接到顶点$v'$​，顶点$v'$​邻接自顶点$v$​。弧$$​和顶点$v$​，$v’$​相关联。以顶点v为头的弧的数目称为v的入度，记为$ID(v0)$​;以$v$​为尾的弧的数目称为v的出度，记为$OD(v)$​​;顶点v的度为$TD(v)=ID(v)+OD(v)$​。一般地，如果顶点$vi$​的度记为$TD(v_i)$​，那么一个有$n$​个顶点，$e$条边或弧的图，满足如下关系$e=\frac 12\sum{i=1}^{n}{TD(v_i)}$。

无向图G=(V,{E})中从顶点$v$​到顶点$v’$​的路径是一个顶点序列$(v=v{i,0},v{i,1},\cdots,v_{i,m}=v’)$​

，其中$(v{i,j-1},v{i,j})\in E,1\leq j\leq m$。如果G是有向图，则路径也是有向的，顶点序列应满足$(v{i,j-1},v{i,j})\in E,1\leq j\leq m$​。路径的长度是路径上的边或弧的数目。第一个顶点和最后一个顶点相同的路径称为回路或环。序列中顶点不重复出现的路径称为简单路径。

在无向图G中，如果从顶点v到顶点v’有路径，则称v和v‘是连通的。如果对于图中任意两个顶点$v_i、v_j\in V$,$v_i$和$v_j$都是连通的，则称G是连通图。连通分量是指无向图中的极大连通子图。

在有向图G中，如果对每一对$v_i,v_j\in V,v_i\neq v_j$,从v_i到v_j和从v_j到v_i都存在路径，则称G是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。

一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。如果​在一棵生成树上添加了一条边，必定构成一个环，因为这条边使得它依附的那两个顶点之间有了第二条路径。

一棵有n个顶点的生成树有且仅有n-1条边。如果一个图有n个顶点和小于n-1条边，则是非连通图。如果它多于n-1条边，则一定有环。但是，有n-1条边的图不一定是生成树。

如果一个有向图恰有一个顶点的入度为0，其余顶点的入度为1，则这是一棵有向树。一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵互不相交的有向树的弧。

图的存储结构

数组表示法

#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
typedef enum{DG,DN,UDG,UDN} GraphKind//{有向图，有向网，无向图，无向网}
typedef struct ArcCell{
    VRType adj;//VRType是顶点关系类型。对无权图，用1或0
    //表示相邻否；对带权图，则为权值类型
    InfoType *info；该弧相关的信息的指针
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
    VertexType vexs[MAX_VERTEX_NUM];//顶点向量
    AdjMatrix arcs;//邻接矩阵
    int vexnum,arcnum;//图的当前顶点数和弧数
    GraphKind kind;//图的种类标志
}MGraph;

邻接表