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

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))

基于英语的理解

我们知道循环一定存在，这是问题的定义，没有循环的情况不需要考虑
对于每对顶点，检查它是否是一条边
如果是边缘，检查我们之前是否去过那里。如果有，我们就找到了循环，并且 return 所有已访问边的大小。（周期大小）
如果不是已访问边，则将其添加到已访问列表中，并继续直到找到源边（将循环增加1直到找到源）

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

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

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

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

Answer 1

因为只有一个环，一个顶点是环的一部分，如果他连接到至少一个其他顶点。由于该图是无向的，因此可以使用以下规则： if a edge between v1 and v2 exists, the edge aswell exists between v2 and v1 或者换句话说：该算法只需要扫描矩阵中给定 v1 < v2 的部分，即使在最坏的情况下，它也减少了 50% 以上的矩阵元素读取数量。由于正在搜索一个循环，我们可以简单地保存在前一个节点之前访问过的每个节点，以确保我们不会再次访问它并结束，如果我们以当前节点等于起始节点结束。

//search for any node that is in the cycle
int firstNode = -1

for int i in 1 , len(graph)
    boolean notIsolated = false

    for int j in 0 , i - 1
         if graph[i][j] == 1
             notIsolated = true
             break

    if notIsolated
         firstNode = i
         break

int node_c = firstNode
int node_p = -1
int count = 0

do
    //search the neighbour that isn't the previous node with above given
    //optimizations
    int n
    for n in 0 , node_c - 1
        if graph[node_c][n] == 1 AND n != node_p
             break

    //update the nodevars for the next step
    node_p = node_c
    node_c = n        

    ++count
while node_c != firstNode //continue until the algorithm reaches the startnode

除此之外，不会有太多优化（至少我不知道有什么办法可以进一步优化运行时）。

Answer 2

给定题中条件（即图中只有边是圈的一部分），圈的长度就是图中边的个数，即图中1的个数的一半邻接矩阵（每条边(i,j)在邻接矩阵中出现两次：A[i,j]=1 and 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) 两次。

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

Graph Theory - Length of Cycle UnDirected Graph - Adjacency Matrix

algorithm

graph

graph-algorithm