[图](2)图的基本术语
图(Graph)是一种较线性表和树更为复杂的数据结构
- 在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继
- 在树型结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素(即其孩子结点)相关，但只能和上一层中一个元素(即其双亲结点)相关；
- 而在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。
由此，图的应用极为广泛，特别是近年来的迅速发展，已渗入到诸如语言学，逻辑学，物理，化学，电讯工程，计算机科学以及数学的其他分支中。
读者在“离散数学”课程中已学习图的理论 [ 可看前言 ]
图的定义和术语
图为一个偶对，由V和E组成的偶对，其中：
图：G=(V,E)
V:顶点(数据元素)的 [有穷非空] 集合;
E:边的 [有穷] 集合;
注意:图里边可以只有 [顶点] 没有 [边]
将G=(V,E)展开就是 Graph=(Vertex,Edge)顶点：图中的数据元素
- 无向图：每条边都是无方向的
- 有向图：每条边都是有方向的
完全图：任意两个点都有一条边相连
无向完全图中：有n个顶点，就有n(n-1)/2条边
有向完全图中：n个顶点，就有n(n-1)条边
稀疏图：有很少的边或弧的图(e<nlogn) [为了区分有向图和无向图，在有向图中，边也叫做弧]
网：等同于赋权图，边或弧带权值的图
邻接：有边或者弧相连的两个顶点之间的关系
- 在无向图当中存在(vi,vj)，则称vi和vj互为邻接点
- 在有向图当中存在<vi,vj>，则称vi邻接到vj，vj邻接于vi
- 用圆括号则表示偶对不含先后关系，若用尖括号表示的偶对则含有先后关系
关联(依附)：边或弧与顶点之间的关系
- 若存在(vi，vj)或<vi,vj>，则称该边/弧关联于vi和vj
顶点的度：与顶点相关联的边的数目，记作TD(v)
- 在有向图中，顶点的度等于该顶点的入度与出度之和
- 顶点v的入度是以v为终点的有向边的条数，记作ID(v)
- 顶点v的出度是以v为起点的有向边的条数，记作OD(v)
有向树：当有向图中仅一个顶点的入度为0，其余顶点的入度均为1
- 与之前树不同的是，上一章的树所相连的叫做分支，而分支是没有方向的
路径：接续的边构成的顶点序列
路径长度：路径上边或弧的数目 / 权值之和
回路/环：第一个顶点和最后一个顶点相同的路径
简单路径：除路径起点和终点可以相同外，其余顶点均不相同
简单回路(简单环)：除路径起点和终点相同外，其余顶点均不相同的路径
连通图(强连通图)：在无(有)向图G=(V,{E})中，若对任何两个顶点v、u都存在从v到u的路径，则称G是连通图(强连通图)
权和网：图中边或弧所具有的相关数称为权，表明从一个顶点到另一个顶点的距离或耗费，带权的图称为网
子图：设有两个图G=(V,{E})、G1=(V1,{E1})，若V1⊆V，E1⊆E，则称G1是G的子图
连通分量(强连通分量)：无向图G的极大连通子图称为G的连通分量
- 极大连通子图的意思是：该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通
有向图G的极大连通子图称为G的强连通分量
- 极大强连通子图意思是：该子图是G的强连通子图，将G的任何不在该子图中的顶点加入，子图不再是强连通的
极小连通子图：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通
生成树：包含无向图G所有顶点的极小连通子图
生成森林：对非连通图，由各个连通分量的生成树的集合
图的抽象类型定义
ADT Graph{
数据对象V:V是具有相同特性的数据元素的集合,称为顶点集
数据对象R:
R = {VR};
VR = { <v,w> | v,w∈V，且P(v,w),<v,w>表示从v到w的弧 ,
谓词P(v,w)定义了弧<v,w>的意义或信息 }
基本操作P：
CreateGraph(&G, V, VR)
初始条件:V是图的顶点集, VR是图中弧的集合
操作结果 : 按V和VR的定义构造图G
DestroyGraph(&G)
初始条件:图G存在
操作结果:销毁图G
LocateVex(G, u)
初始条件:图G存在, u和G中顶点有相同特征
操作结果:若G中存在顶点u, 则返回该顶点在图中位置
GetVex(G,x)
初始条件:图G存在,v是G中某个顶点
操作结果:返回v的值
PutVex(G,x)
初始条件:图G存在,v是G中某个顶点
操作结果:对v赋值value
FirstAdjVex(G,v)
初始条件:图G存在,v是G中某个顶点
操作结果:返回v的第一个邻接顶点,若顶点在G中没有邻接顶点,则返回“空”
NextAdjVex(G,v,w)
初始条件:图G存在,v是G中某个顶点,w是v的邻接顶点
操作结果:返回v的(相对于w的)下一个邻接顶点,若w是v的最后一个邻接点,则返回“空”
InsertVex(&G,v)
初始条件:图G存在,v和图中顶点有相同特征
操作结果:在图G中增添新顶点v
DeleteVex(&G,v)
初始条件:图G存在,v是G中某个结点
操作结果:删除G中顶点v及其相关的弧
InsertArc(&G,v,w)
初始条件:图G存在,v和w是G中两个顶点
操作结果:在G中增添弧<v,w>,若G是无向的,则还增添对称弧<w,v>
DeleteArc(&G,v,w)
初始条件:图G存在,v和w是G中两个顶点
操作结果:在G中删除弧<v,w>,若G是无向的,则还删除对称弧<w,v>
DFSTraverse(G,Visit())
初始条件:图G存在,Visit是顶点的应用函数
操作结果:对图进行深度优先遍历,在遍历过程中对每个顶点调用函数Visit一次
且仅一次,一旦Visit()失败,则操作失败
BFSTraverse(G,Visit())
初始条件:图G存在,Visit是顶点的应用函数
操作结果:对图进行广度优先遍历,在遍历过程中对每个顶点调用函数Visit一次
且仅一次,一旦Visit()失败,则操作失败
}ADT Graph在前述图的基本操作定义中，关于“顶点的位置”和“邻接点的位置“只是一个相对的概念，因为，从图的逻辑结构定义来看，图中的顶点之间不存在全序的关系(即无法将图中顶点排列成一个线性序列)，任何一个顶点都可被看成是第一个顶点；另一方面，任一顶点的邻接点之间也不存在次序关系。
但为了操作方便，我们需要将图中顶点按任一的顺序排列起来(这个排列关系和VR无关)，由此，所谓“顶点在图中的位置”指的是该顶点在这个人为的随意排列中的位置(或序号)，同理，可对某个顶点的所有邻接点进行排队，在这个排队中自然形成了第一个或第k个邻接点，若某个顶点的邻接点的个数大于k，则称第k+1个邻接点为第k个邻接点的下一个邻接点，而最后一个邻接点的下一个邻接点为“空”。