python - 如何在 python 中的二进制矩阵中跟踪 1 的所有唯一路径？

Question

目标是创建每个节点都被访问一次的所有路径。 1 代表可行的路线，0 代表不存在路线。

例子:

假设我有一个矩阵

   1  2  3  4  5  6  7
1 [0  1  0  1  0  0  1]
2 [1  0  1  0  0  1  0]
3 [0  1  0  0  1  0  0]
4 [1  0  0  0  0  0  0]
5 [0  0  1  0  0  0  0]
6 [0  1  0  0  0  0  1]
7 [1  0  0  0  0  1  0]

为了这个例子，让我们从 4 开始

那么所有可能的路径都是:(有点像旅行商问题)

[4,1,2,3,5]
[4,1,2,6,7]
[4,1,7,6,2,3,5]

我将矩阵存储为二维数组:

M0 =[[0, 1, 0, 1, 0, 0, 1],
     [1, 0, 1, 0, 0, 1, 0],
     [0, 1, 0, 0, 1, 0, 0],
     [1, 0, 0, 0, 0, 0, 0],
     [0, 0, 1, 0, 0, 0, 0],
     [0, 1, 0, 0, 0, 0, 1],
     [1, 0, 0, 0, 0, 1, 0]]

这是我正在尝试的一些东西，但它们不起作用，因为它不会重置回它分支所在的最近坐标。

我也认为这可能不是最好的方法，我正在尝试实现贪婪方法的一些变体。一定有比修复此代码更好的方法。

path=[]
allPaths=[]
visited=[]
branchAt=[]

def route():
tempMatrix = genMat() #set this to the above example matrix if you trying to run this code
column = 3 #Starting with a static column for now

#while(column+1 not in path):

for counter in range(0,20):   #Static loop as well

    path.append(column+1)
    delMat(tempMatrix[column]) #Sets all the elements to 0 in that row of the tempMatrix so same path isn't visited twice in subsequent interations (ie when in another column)

    oneCount=0  #check if path can branch out in the current column (aka more than one 1's)
    for row in range(0,len(matrix)):
        if(tempMatrix[row][column]==1):
            oneCount+=1

    for row in range(0,len(matrix)): 
        coOrds=([column+1,row+1])
        if(tempMatrix[row][column]==1):
            #if (coOrds) not in visited and oneCount>1:
            if oneCount>1 and coOrds in visited:
                continue
            else:
                if(oneCount>1):
                    visited.append(coOrds)
                    if len(branchAt)<1:
                        branchAt.append(coOrds)
                column=row
                delMat(tempMatrix[row])
                break
            # else:
            #     if(oneCount>1):
            #         continue
            # else:
            #     continue
        else:
            if(row==len(matrix)-1):
                print("Final Path: ",path)
                allPaths.append(tuple(path))
                bran.clear()
                break

print("allPaths: ", allPaths)
print("Visited: ", visited)

Answer 1

使用来自 https://www.geeksforgeeks.org/find-paths-given-source-destination/ 的算法

修改路径打印以使用您的节点编号(即从 1 而不是 0 开始)

from collections import defaultdict 

#This class represents a directed graph  
# using adjacency list representation 
class Graph: 

    def __init__(self,vertices): 
        #No. of vertices 
        self.V= vertices  

        # default dictionary to store graph 
        self.graph = defaultdict(list)  

    # function to add an edge to graph 
    def addEdge(self,u,v): 
        self.graph[u].append(v) 

    '''A recursive function to print all paths from 'u' to 'd'. 
    visited[] keeps track of vertices in current path. 
    path[] stores actual vertices and path_index is current 
    index in path[]'''
    def printAllPathsUtil(self, u, d, visited, path): 

        # Mark the current node as visited and store in path 
        visited[u]= True
        path.append(u+1)  # add 1 so print output starts at 1

        # If current vertex is same as destination, then print 
        # current path[] 
        if u ==d: 
            print (path)
        else: 
            # If current vertex is not destination 
            #Recur for all the vertices adjacent to this vertex 
            for i in self.graph[u]: 
                if visited[i]==False: 
                    self.printAllPathsUtil(i, d, visited, path) 

        # Remove current vertex from path[] and mark it as unvisited 
        path.pop() 
        visited[u]= False


    # Prints all paths from 's' to 'd' 
    def printAllPaths(self,s, d): 

        # Mark all the vertices as not visited 
        visited =[False]*(self.V) 

        # Create an array to store paths 
        path = [] 

        # Call the recursive helper function to print all paths 
        self.printAllPathsUtil(s, d,visited, path) 

def generate_paths(A):
  g = Graph(len(A))
# We loop over all row, column combinations and add edge
# if there is a connection between the two nodes
  for row in range(len(A)):
    for column in range(len(A[0])):
      if A[row][column] == 1:
        g.addEdge(row, column)

  for row in range(len(A)):
    # show row+1, so row numbering prints starting with 1
    print (f"Following are all different paths starting at {row+1}")
    for column in range(row+1, len(A[0])):
        g.printAllPaths(row, column)


A =[[0,  1,  0,  1,  0,  0 , 1],
    [1,  0,  1,  0,  0 , 1,  0],
    [0,  1,  0,  0,  1,  0,  0],
    [1,  0,  0,  0,  0,  0,  0],
    [0,  0,  1,  0,  0,  0,  0],
    [0,  1,  0,  0,  0,  0,  1],
    [1,  0,  0,  0,  0,  1,  0]]

generate_paths(A)

输出

Following are all different paths starting at 1
[1, 2]
[1, 7, 6, 2]
[1, 2, 3]
[1, 7, 6, 2, 3]
[1, 4]
[1, 2, 3, 5]
[1, 7, 6, 2, 3, 5]
[1, 2, 6]
[1, 7, 6]
[1, 2, 6, 7]
[1, 7]
Following are all different paths starting at 2
[2, 3]
[2, 1, 4]
[2, 6, 7, 1, 4]
[2, 3, 5]
[2, 1, 7, 6]
[2, 6]
[2, 1, 7]
[2, 6, 7]
Following are all different paths starting at 3
[3, 2, 1, 4]
[3, 2, 6, 7, 1, 4]
[3, 5]
[3, 2, 1, 7, 6]
[3, 2, 6]
[3, 2, 1, 7]
[3, 2, 6, 7]
Following are all different paths starting at 4
[4, 1, 2, 3, 5]
[4, 1, 7, 6, 2, 3, 5]
[4, 1, 2, 6]
[4, 1, 7, 6]
[4, 1, 2, 6, 7]
[4, 1, 7]
Following are all different paths starting at 5
[5, 3, 2, 1, 7, 6]
[5, 3, 2, 6]
[5, 3, 2, 1, 7]
[5, 3, 2, 6, 7]
Following are all different paths starting at 6
[6, 2, 1, 7]
[6, 7]
Following are all different paths starting at 7