查找图中的最短循环（无向、无权）

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

查找图中的最短循环（无向、无权）

Find the shortest cycle in a graph (Undirected, Unweighted)

python

algorithm

graph

graph-algorithm

python-3.x