简单路径定义
如果路径上的各顶点均不互相重复,称这样的路径为简单路径。如果路径上的第一个顶点与最后一个顶点重合,这样的路径称为回路(cycle)或环或圈。如在图1中,回路有
等等 。
简单路径相关概念
图结构是由有限非空顶点集合V和边集合E组成的一种数据结构。记作。顶点具有数据元素,边表示任意两个顶点和之间的关系,记作。若图G中与不等价,则称G为有向图;若与等价,则称G为无向图,并以无序对代替两个有序对和。图中每条边可以有一个称为权的数与之相连,权可以表示两个顶点之间的距离或从一个顶点到另一个顶点的代价,这种带权的图通常称为网 。
图中,从顶点到顶点的路径为一顶点序列,其中。路径上的顶点都不相同的路径称为简单路径。第一个顶点与最后一个顶点相同的路径称为回路或环。除了第一个顶点与最后一个顶点外,其余顶点都不重复的回路,称为简单回路。若从顶点到顶点至少存在一条路径,则称和是连通的。若图中任意两个顶点都是连通的,则称为连通图。
在计算机中,通常采用以下几种存储结构来表示图结构。
(1)数组法。用一个一维数组存储各顶点的数据信息,用一个二维数组表示的邻接矩阵表示边的集合。其中邻接矩阵A是一个n阶方阵(n为图中顶点的个数)。
(2)邻接表法。对图中每个顶点建立一个单链表。在顶点对应的单链表中各结点表示以为初始点的一条边,再用一个数组存储各顶点的数据信息和指向其对应的单链表的指针。
除以上两种常用表示法外,还有二进制向量表示法、邻接多重表和十字链表等表示方法。
图的基本操作有查找、插入和删除,以及求两个顶点间的路径及路径长度、图的遍历和求连接于某一顶点的边数等 。