algorithm - 图论 - 循环长度无向图 - 邻接矩阵

Question

算法部分综合考试的复习题。

Let G be an undirected Graph with n vertices that contains exactly one cycle and isolated vertices (i.e. no leaves). That means the degree of a vertex is 0 (isolated) if it is not in the cycle and 2 if it is part of the cycle. Assume that the graph is reresented by an adjacency matrix. Describe an efficeint algorithm that finds the length of the cycle.

我正在寻求帮助来验证我的理解，检查它是否正确以及分析是否也正确。

我的答案(伪pythonic)

visited = [] // this will be list of u,v pairs belonging to cycle

for each u,v in G[][]:
    if G[u][v] == 1:      // is an edge
        if G[u][v] in visited : // 
            return len(visited) // return the length of the cycle, since weve hit begining of cycle
        else :
             visited.add((u,v))

基于英语的理解

• 我们知道循环一定存在，是问题的定义，没有发现循环的情况不需要考虑

• 对于每对顶点，检查它是否是一条边

• 如果它是一条边，检查我们之前是否去过那里。如果有，我们就找到了循环，并返回所有访问过的边的大小。 (周期大小)

• 如果不是已访问边，则将其添加到已访问列表中，并继续直到我们找到源边(将循环增加 1 直到我们到达源)

我认为我的分析可能不对。因为我们至少访问每个 (u,v) 对一次，然后检查它是否是一条边，以及每条边进行 2 次比较。我认为它涉及到 O(|v|^2 + 2 |E|)

• 顶点数，平方(因为我们访问了矩阵中的每一对)，每条边 + 2 次比较。

有人可以就效率和正确性提出建议吗？如果我在不承认逻辑证明的情况下做出了逻辑上的飞跃，也可以提供更多基于英语的理解？

感谢阅读并提前感谢您的帮助。

Answer 1

给定题中条件(即图中只有边是环的一部分)，环的长度就是图中边的个数，即邻接矩阵中1个数的一半(每条边 (i, j) 在邻接矩阵中出现两次:A[i,j]=1 和 A[j,i]=1)。

因此，显而易见的算法是将邻接矩阵的条目相加并除以 2。如果有 V 个顶点，则为 O(V^2)。

看起来可能有帮助的一件事是，一旦您在邻接矩阵中找到第一个 1，就沿着边走，直到您回到起点:

Find i, j such that A[i, j]=1.
start = i
cycle_length = 1
repeat
    find k != i with A[j, k] = 1
    i, j = j, k
    cycle_length++
until i = start

此过程终止后，cycle_length 为循环的长度。不过，这仍然是最坏情况 O(V^2)，尽管如果您可以快速找到循环上的单个顶点，则它是 O(V*C)，其中 C 是循环的长度。

您问题中的代码不起作用。您正在迭代 (u, v) 作为矩阵中的索引，并且不可能两次找到相同的 (u, v)。