路径

图论中一个非常重要的概念是路径,路径是指一个有限或无限的边序列,这些边连接着一系列点。

路径的类型分为三种:walktrailpath。关于路径的详细说明,请参见维基百科#Walk,_trail,_path)。

本文以下图为例进行简单介绍。

路径示例

walk

walk类型的路径由有限或无限的边序列构成。遍历时点和边可以重复。

查看示例图,由于C、D、E构成了一个环,因此该图包含无限个路径,例如A->B->C->D->EA->B->C->D->E->CA->B->C->D->E->C->D

trail

trail类型的路径由有限的边序列构成。遍历时只有点可以重复,边不可以重复。柯尼斯堡七桥问题的路径类型就是trail

查看示例图,由于边不可以重复,所以该图包含有限个路径,最长路径由5条边组成:A->B->C->D->E->C

在trail类型中,还有 cyclecircuit 两种特殊的路径类型,以下图为例对这两种特殊的路径类型进行介绍。

trail示例

  • cycle

    cycle 是封闭的 trail 类型的路径,遍历时边不可以重复,起点和终点重复,并且没有其他点重复。在此示例图中,最长路径由三条边组成:A->B->C->AC->D->E->C.

  • circuit

    circuit 也是封闭的 trail 类型的路径,遍历时边不可以重复,除起点和终点重复外,可能存在其他点重复。在此示例图中,最长路径为:A->B->C->D->E->C->A

path

path类型的路径由有限的边序列构成。遍历时点和边都不可以重复。

查看示例图,由于点和边都不可以重复,所以该图包含有限个路径,最长路径由4条边组成:A->B->C->D->E

视频

用户也可以观看视频了解路径的相关概念。

Nebula Algorithm(03分09秒)