python - 返回无向图中的顶点

Question

我正在尝试在 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

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

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