[科普中国]-简单路径

简单路径有两个义项，可以指图G(V，E)中路径上的顶点都不相同的路径，还可以指Rn中的弧，亦称简单弧，是曲线弧概念的推广。

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

等等1。

相关概念图结构是由有限非空顶点集合V和边集合E组成的一种数据结构。记作。顶点具有数据元素，边表示任意两个顶点和之间的关系，记作。若图G中与不等价，则称G为有向图；若与等价，则称G为无向图，并以无序对代替两个有序对和。图中每条边可以有一个称为权的数与之相连，权可以表示两个顶点之间的距离或从一个顶点到另一个顶点的代价，这种带权的图通常称为网2。

图中，从顶点到顶点的路径为一顶点序列，其中。路径上的顶点都不相同的路径称为简单路径。第一个顶点与最后一个顶点相同的路径称为回路或环。除了第一个顶点与最后一个顶点外，其余顶点都不重复的回路，称为简单回路。若从顶点到顶点至少存在一条路径，则称和是连通的。若图中任意两个顶点都是连通的，则称为连通图。

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

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

(2)邻接表****法。对图中每个顶点建立一个单链表。在顶点对应的单链表中各结点表示以为初始点的一条边，再用一个数组存储各顶点的数据信息和指向其对应的单链表的指针。

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

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

Rn中的弧Rn中的弧(arc in Rn)亦称简单弧，是曲线弧概念的推广，它有两种不同的定义，一种定义是指连续的单射(这样，弧是特殊的路径)；另一种定义是指这样的的值域。后一种定义更具几何含义，按照它，弧是自身不相交的曲线，或曲线上任意两点间不包含重点的部分。采用这种定义时，又称为若尔当弧，同时，把前一种定义中的称为简单路径3。

本词条内容贡献者为:

王海侠 - 副教授 - 南京理工大学