如何证明一种线性算法可以识别图中的所有环和长度，其中每个顶点只有一个出边

Question

Consider a directed graph on n vertices, where each vertex has exactly one outgoing edge. This graph consists of a collection of cycles as well as additional vertices that have paths to the cycles, which we call the branches. Describe a linear time algorithm that identifies all of the cycles and computes the length of each cycle. You can assume that the input is given as an array A, where A[i] is the neighbor of i, so that the graph has the edge (i, A[i]).

到目前为止，我的算法方法基本上是标记我已经遍历的顶点，每次一个顶点指向我已经遍历的顶点时，我计算一个循环并移动到下一个未访问的顶点。在这个过程中，我还有一个hashmap什么的，用来记录遍历每个节点的顺序，这样我就可以在识别到一个循环的时候计算长度。（那会是线性的吗？）但是，我对证明还很陌生，我不知道如何证明算法的正确性。

Answer 1

如果允许使用额外的内存，Python中的算法将是这样。

colors = [0] ** N; # initialize N element array withe values of zero (not seen)
for i in range(N):
    v = i # current vertex
    if colors[v] != 0: continue # already seen
    colors[v] = 1 # seen
    v = A[v] # move to neighbor
    while colors[v] == 0:
       colors[v] = 1
       v = A[v] # move to neighbor
    # we have reached previously seen node; this is the start node of a cycle
    colors[v] = 2 # mark the start of a cycle
    cycle_len = 1
    v = A[v] # move to neighbor
    while colors[v] == 1:
       cycle_len += 1
       v = A[v] # move to neighbor
   print("got a cycle with length =", cycle_len)

基本思路是用三种颜色分别标记已经访问过的节点和循环起点的节点；显然，单个节点只能属于单个循环。

该算法是线性的，因为内部 while 循环仅针对以前未见过的节点执行。跳过已经看到的节点。在最坏的情况下，两个内部 while 循环都已完全执行，但 2*N 仍然是 O(N)。

使用散列映射不符合要求，因为散列映射的最坏情况时间复杂度不是线性的。

如何证明一种线性算法可以识别图中的所有环和长度，其中每个顶点只有一个出边

How to prove a linear algorithm that identifies all cycles and the length in a graph where each vertex has exactly one outgoing edge

algorithm

graph-theory

graph-algorithm