无向图中的返回顶点

Question

我试图在Python中提出一种贪婪的算法，该算法在给定某个起始顶点的情况下返回无向图中的顶点。我知道DFS确定是否存在循环，但我正在尝试实际返回形成循环的顶点。我使用邻接矩阵来表示下图：

adjacencyMatrix = [[0, 1, 1, 0], [1, 0, 0, 1], [1, 0, 0, 1], [0, 1, 1, 0]]

从图学上讲，这是一个由单个循环组成的无向图。

我当前的思想过程是将起始索引设置为我遇到的第一个＜code＞1）。然后我会查看行的其余部分，看看是否有另一个＜code＞1＜/code＞存在，因为这意味着我的当前顶点连接到该索引。然而，我不能完全确定（a）这是正确的方法，以及（b）如何“移动”到下一个顶点。例如，如何导航嵌套的＜code＞For顶点移动到＜code＞相邻矩阵[0][2]

编辑我想出的这个解决方案似乎对我尝试的几幅图有效:

def findCycle(matrix):
    visited = list()
    cycleNotFound = True
    row = 0
    col = 0
    startVertex = (0, 0)

    while cycleNotFound:

        # Only add a vertex if it has not already been visited
        if (matrix[row][col] == 1) and ((row, col) not in visited):
            # Set the startVertex when the first node is found
            if len(visited) == 0:
                startVertex = (row, col)

            # Add the current vertex and its counter part
            visited.append((row, col))
            visited.append((col, row))

            # If row and col are equal, infite loop will get created
            if row != col:
                row = col
                col = 0
            else:
                row += 1

        # If back at starting point, break look
        elif ((row, col) == startVertex) and (len(visited) > 1):
            cycleNotFound = False
            visited.append(startVertex)

        # Else, continue to look for unvisted neighbors
        else:
            col += 1

    return visited

if __name__ == "__main__":
    matrix = [[0, 1, 1, 0], [1, 0, 0, 1], [1, 0, 0, 1], [0, 1, 1, 0]]
    cycle = findCycle(matrix)
    index = 0
    # Print the vertices.  Only print even vertices to avoid duplicates.
    while (index < len(cycle)):
        print cycle[index]
        index += 2

这并不是最优雅的解决方案，我确信需要进行一些重大的重构。

Answer 1

你可以试试这个：

def findCycle(node):
    cycle = stack()
    if( DFS(node, cycle) ):
        return cycle
    return None

def DFS(node, cycle):
    cycle.append(node)
    mark node as visited
    foreach node.neighbors as neighbor:
        if neighbor already visited:
            return true
        else:
            if( DFS(neighbor, cycle) ) return true
    cycle.remove(node)
    return false