在無向圖中返回頂點

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]頂點移動到頂點？我只需交換行和列索引？

編輯 該解決方案，我想出了，似乎對一些圖形我試了一下工作：

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