1

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

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

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

我目前的思考过程是将我的起始索引设置为1我遇到的第一个索引（在这种情况下adjacencyMatrix[0][1]）。然后我会查看该行的其余部分，看看是否1有另一个，因为这意味着我当前的顶点连接到该索引。但是，我不完全确定（a）这是否是正确的方法以及（b）如何“移动”到下一个顶点。例如，我将如何导航我的嵌套for循环以从adjacencyMatrix[0][1]顶点移动到adjacencyMatrix[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

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

4

1 回答 1

2

你可以试试这个：

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
于 2015-05-04T06:08:28.280 回答