|
|
|
图是比树结构更复杂的一种数据结构。在树结构中，可认为除根结点没有前驱结点外，其余的每个结点只有唯一的一个前驱（双亲）结点和多个后继（子树）结点。而在图结构中，任意两个结点之间都可能有直接的关系，所以图中一个结点的前驱和后继的数目是没有限制的。图结构被用于描述各种复杂的数据对象，在自然科学、社会科学和人文科学等许多领域有非常广泛的应用。
|
|
|
|
|
|
图G是由两个集合V和E构成的二元组，记作G=（V，E），其中V是图中顶点的非空有限集合，E是图中边的有限集合。从数据结构的逻辑关系角度来看，图中任一顶点都有可能与图中其他顶点有关系，而图中所有顶点都有可能与某一顶点有关系。在图中，数据结构中的数据元素用顶点表示，数据元素之间的关系用边表示。
|
|
|
|
.有向图：若图中每条边都是有方向的，则称为有向图。从顶点νi到νj的有向边<vi，vj>也称为弧，起点νi称为弧尾；终点νj称为弧头。在有向图中，<νi，νj>与<νj，vi>分别表示两条弧，如下图（a）所示。
|
|
|
|
|
|
|
|
.无向图：若图中的每条边都是无方向的，顶点νi和νj之间的边用（νi，νj）表示。在无向图中，（νi，νj）与（νj，νi）表示的是同一条边。5个顶点的一个无向图如上图（b）所示。
|
|
|
|
.完全图：若一个无向图具有n个顶点，而每一个顶点与其他n-1个顶点之间都有边，则称之为无向完全图。显然，含有n个顶点的无向完全图共有n（n-1）/2条边。类似地，有n个顶点的有向完全图中弧的数目为n（n-1），即任意两个不同顶点之间都存在方向相反的两条弧。
|
|
|
|
.度、出度和入度：顶点ν的度是指关联于该顶点的边的数目，记作D（ν）。若G为有向图，顶点的度表示该顶点的入度和出度之和。顶点的入度是以该顶点为终点的有向边的数目，而顶点的出度指以该顶点为起点的有向边的数目，分别记为ID（ν）和OD（ν）。例如，上图（a）中，顶点1，2，3，4的入度分别为1，2，1，1，出度分别为3，0，0，2。上图（b）中，顶点1，2，3，4，5的度分别为3，2，4，3，2。
|
|
|
|
.路径：在无向图G中，从顶点νp到顶点νq的路径是指存在一个顶点序列νp，νi1，νi2，…，νin，νq，使得（νp，νi1），（νi1，νi2），…，（νin，νq）均属于E（G）。若G是有向图，其路径也是有方向的，它由E（G）中的有向边<νp，νi1>，<νi1，νi2>，…，<νin，νq>组成。路径长度是路径上边或弧的数目。第一个顶点和最后一个顶点相同的路径称为回路或环。若一条路径上除了νp和νq可以相同外，其余顶点均不相同，这种路径称为一条简单路径。
|
|
|
.子图：若有两个图G=（V，E）和G'=（V'，E'），如果 且 ，则称G'为G的子图。
|
|
|
|
.连通图：在无向图G中，若从顶点νi到顶点νj有路径，则称顶点νi和顶点νj是连通的。如果无向图G中任意两个顶点都是连通的，则称其为连通图。上图（b）所示的无向图是连通图。
|
|
|
|
.强连通图：在有向图G中，如果对于每一对顶点νi，νj∈V且νi≠νj，从顶点νi到顶点νj和从顶点νj到顶点νi都存在路径，则称图G为强连通图。上图（a）所示的有向图不是强连通图。以顶点1和顶点3为例，顶点1至顶点3存在路径，而顶点3至顶点1没有路径。
|
|
|
|
|
|
从图的逻辑结构的定义来看，图中的顶点之间不存在全序关系（即无法将图中的顶点排列成一个线性序列），任何一个顶点都可被看成第一个顶点；另一方面，任一顶点的邻接点之间也不存在次序关系。为便于运算，为图中每个顶点赋予一个序号。
|
|
|
|
|
|
|
|
|
|
邻接矩阵表示法利用一个矩阵来表示图中顶点之间的关系。对于具有n个顶点的图G=（V，E）来说，其邻接矩阵是一个n阶方阵，且满足：
|
|
|
|
|
|
有向图和无向图的邻接矩阵如下图中的矩阵A和B所示。
|
|
|
|
|
|
|
|
由邻接矩阵的定义可知，无向图的邻接矩阵是对称的，而有向图的邻接矩阵则不一定具有该性质。
|
|
|
|
借助于邻接矩阵，可判定任意两个顶点之间是否有边（或弧）相连，并且容易求得各个顶点的度。对于无向图，顶点νi的度是邻接矩阵中第i行（或列）的值不为0的元素数目（或元素的和）；对于有向图，第i行的元素之和为顶点νi的出度OD（νi），第j列的元素之和为顶点νj的入度ID（νj）。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
邻接链表指的是为图的每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点νi的边（对于有向图是以νi为尾的弧）。邻接链表中的结点有表结点和表头结点两种类型，如下所示：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
这些表头结点通常以顺序结构的形式存储，以便随机访问任一顶点及其邻接表。若图用邻接链表来表示，则对应的数据类型可定义如下：
|
|
|
|
|
|
显然，对于有n个顶点、e条边的无向图来说，其邻接链表需要n个头结点和2e个表结点，如下图所示。对于无向图的邻接链表，顶点νi的度恰为第i个邻接链表中表结点的数目。
|
|
|
|
|
|
|
|
下图（b）是下图（a）所示有向图的邻接表。从中可以看出，由于第i个邻接链表中表结点的数目只是顶点νi的出度，因此必须逐个扫描每个顶点的邻接表，才能求出一个顶点的入度。为此，可以建立一个有向图的逆邻接链表，如下图（c）所示。
|
|
|
|
|
|
|
