目标是创建每次访问每个节点的所有路径。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)
最佳答案
使用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
关于python - 如何在python的二进制矩阵中跟踪所有1的唯一路径？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57934177/