建设工程知识

简单路径图论中的简单路径

简单路径定义

如果路径上的各顶点均不互相重复，称这样的路径为简单路径。如果路径上的第一个顶点与最后一个顶点重合，这样的路径称为回路(cycle)或环或圈。如在图1中，回路有

等等 。

简单路径相关概念

图结构是由有限非空顶点集合V和边集合E组成的一种数据结构。记作

。顶点具有数据元素，边表示任意两个顶点

和

之间的关系，记作

。若图G中

与

不等价，则称G为有向图；若

与

等价，则称G为无向图，并以无序对

代替两个有序对

和

。图中每条边可以有一个称为权的数与之相连，权可以表示两个顶点之间的距离或从一个顶点到另一个顶点的代价，这种带权的图通常称为网 。

图

中，从顶点

到顶点

的路径为一顶点序列

，其中

。路径上的顶点都不相同的路径称为简单路径。第一个顶点与最后一个顶点相同的路径称为回路或环。除了第一个顶点与最后一个顶点外，其余顶点都不重复的回路，称为简单回路。若从顶点

到顶点

至少存在一条路径，则称

和

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

在计算机中，通常采用以下几种存储结构来表示图结构。

(1)数组法。用一个一维数组存储各顶点的数据信息，用一个二维数组表示的邻接矩阵表示边的集合。其中邻接矩阵A是一个n阶方阵(n为图中顶点的个数)。

(2)邻接表法。对图中每个顶点建立一个单链表。在顶点

对应的单链表中各结点表示以

为初始点的一条边，再用一个数组存储各顶点的数据信息和指向其对应的单链表的指针。

除以上两种常用表示法外，还有二进制向量表示法、邻接多重表和十字链表等表示方法。

图的基本操作有查找、插入和删除，以及求两个顶点间的路径及路径长度、图的遍历和求连接于某一顶点的边数等 。

• 上一篇：轴流式消防排烟风机
• 下一篇：事故频发警示涂料企业安全生产势在必行
• 关键词： 简单路径图论中的简单路径 简单路径