在图中寻找最短的循环（无向，无权）

Question

我一直在尝试编写一个python程序，在一个图中找到最短的循环，但我被卡住了。这是我的密码：

def shortestCycle(vertices):

    distances = []

    for i in range(len(vertices.keys())):
        dist = 0
        visited = []
        vertex = list(vertices.keys())[i]
        searchQueue = deque()

        searchQueue += vertices[vertex]

        while searchQueue:
            currentVertex = searchQueue.popleft()   
            if currentVertex not in visited:

                if currentVertex == vertex:
                    break
                else:
                    visited.append(currentVertex)
                    searchQueue += vertices[currentVertex]
            dist += 1
        distances.append(udaljenost)


    return min(distances)

作为额外的解释，vertices是一个字典，顶点作为键，它们的邻域作为值，例如：{1 : [2, 4, 5, 8], 2 : [1, 3], ...。这段代码给出了错误的结果，我也知道是什么导致了这种情况，但我不知道如何修复它。有什么想法或建议吗？你知道吗

编辑：

输入示例：{'1': ['2', '4', '5', '8'], '2': ['1', '3'], '3': ['2', '4'], '4': ['1', '3'], '5': ['1', '6'], '6': ['5', '7'], '7': ['6', '8'], '8': ['1', '7']}

输出示例：4

Answer 1

我设法解决了这个问题：

def shortestCycle(vertices):


    minCycle = sys.maxsize
    n = len(vertices.keys())

    for i in range(n):

        distances = [sys.maxsize for i in range(n)]
        parent = [-1 for i in range(n)]

        distances[i] = 0


        q = deque()
        q.append(i + 1)


        while q:

            currentVertex = str(q.popleft())


            for v in vertices[currentVertex]:

                j = currentVertex
                if distances[v - 1] == sys.maxsize:
                    distances[v - 1] = 1 + distances[j - 1]

                    parent[v - 1] = j

                    q.append(v)

                elif parent[j - 1] != v and parent[v - 1] != j - 1:

                    minCycle = min(minCycle, distances[j - 1] + distances[v - 1] + 1)

        if minCycle == sys.maxsize:
            return -1
        else:
            return minCycle