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

これは最も洗練されたソリューションではなく、実行する必要がある大きなリファクタリングがいくつかあると確信しています。