我正在尝试对有向图进行深度优先搜索，同时我还尝试跟踪有关该图的数据。首先，这是我用来构造有向图的类。
class Node(object):
def __init__(self, name):
self.name = str(name)
def getName(self):
return self.name
def __str__(self):
return self.name
def __repr__(self):
return self.name
def __eq__(self, other):
return self.name == other.name
def __ne__(self, other):
return not self.__eq__(other)
class Edge(object):
def __init__(self, src, dest,distance,distance_out):
self.src = src
self.dest = dest
self.distance = distance
self.distance_out = distance_out
def getSource(self):
return self.src
def getDestination(self):
return self.dest
def getDistance(self):
return self.distance
def getDistance_Outdoors(self):
return self.distance_out
def __str__(self):
return str(self.src) + '--'+'Total Distance:(' +str(self.distance)+')' + ' '+ 'Outside Distance:('+str(self.distance_out)+')'+'-->' + str(self.dest)
class Digraph(object):
"""
A directed graph
"""
def __init__(self):
self.nodes = set([])
self.edges = {}
def addNode(self, node):
if node in self.nodes:
raise ValueError('Duplicate node')
else:
self.nodes.add(node)
self.edges[node] = []
def addEdge(self, edge):
src = edge.getSource()
dest = edge.getDestination()
distance = edge.getDistance()
distance_out = edge.distance_out
if not(src in self.nodes and dest in self.nodes):
raise ValueError('Node not in graph')
self.edges[src].append([dest,[distance,distance_out]])
def childrenOf(self, node):
return self.edges[node]
def hasNode(self, node):
return node in self.nodes
def testDict(self):
return self.edges
def __str__(self):
res = ''
for k in self.edges:
for d in self.edges[k]:
res = res + str(k) + '->' + str(d[0]) + str(d[1])+ '\n'
return res[:-1]
我当前正在处理的有向图有 37 个节点和 129 条边。
这是我的搜索功能的代码。
import string
from graph import Digraph, Edge, Node
def depthFirstSearchVisit(digraph, time, node,discovered, undiscovered ,
explored , nodes , hierarchy ):
time = time + 1 #While vertex has just been discovered
nodes[node].append(time) ##Mark the discovery time for the node in the nodes dictionary
discovered.append(node)##Mark the node as discovered
if node in undiscovered: ## Remove node from undiscovered after it's discovery
undiscovered.remove(node)
for adjacent_node in digraph.childrenOf(node):##Explore edge (node, adjacent_node)
if adjacent_node[0] in undiscovered: ##The adjacent node is a predecessor of the node
hierarchy[node].append(adjacent_node[0])##Mark it as such in the hierarchy dictionary
depthFirstSearchVisit(digraph,time,adjacent_node[0],discovered,
undiscovered,explored,nodes,hierarchy)##Then recursively visit that adjacent_node
explored.append(node) ##After exploring all of the nodes adjacent
nodes[node].append(time)
return nodes
def depthFirstSearch(digraph,time, discovered = [], undiscovered = [],
explored = [], nodes = {}, hierarchy = {}):
if len(nodes) == 0: ## If nodes is empty
for i in digraph.nodes: ##Initialize a dictionary where nodes are the keys and
nodes[i] = [] ##An empty list for values, so they can be filled with discovery and exploration times
for key in nodes: ##For each node in the digraph mark them all as undiscovered.
undiscovered.append(key)
for key2 in nodes:##Construct hierarchy dict for later use in DepthFirstSearchVisit
hierarchy[key2] = []
##Time initialized to zero in parameter call
for node in nodes:
if node in undiscovered:
depthFirstSearchVisit(digraph,time,node,discovered, undiscovered, explored,nodes,hierarchy)
return nodes
现在我正在测试字典节点是否输出正确的信息。这是节点字典的结构。
{node: [time of discovery, time of exploration]}
发现时间是当 DepthFirsTSearchVisit 第一次遇到一个节点时，而探索时间是当该节点的后代等等一直向下都被发现时。
这是我得到的输出:
{32: [1, 1], 48: [4, 4], 50: [9, 9], 37: [17, 17], 13: [15, 15], 10: [25, 25], 64: [9, 9], 35: [18, 18], 5: [22, 22], 24: [14, 14], 6: [10, 10], 57: [2, 2], 9: [20, 20], 68: [6, 6], 39: [16, 16], 1: [23, 23], 38: [16, 16], 62: [8, 8], 4: [12, 12], 16: [4, 4], 34: [15, 15], 2: [9, 9], 54: [7, 7], 7: [21, 21], 66: [8, 8], 56: [5, 5], 46: [3, 3], 76: [7, 7], 18: [6, 6], 3: [24, 24], 36: [2, 2], 12: [13, 13], 33: [19, 19], 14: [8, 8], 8: [11, 11], 26: [3, 3], 31: [18, 18]}
我认为我应该得到什么输出:时间值不应该相同。发现和探索之间应该有很大的区别。
预先感谢您的帮助。
最佳答案
您将时间视为传递引用。它不是——它是按值传递的。这是因为 python 整数是不可变的。所以当你这样做时:
def depthFirstSearchVisit(digraph, time, node,discovered, undiscovered ,
explored , nodes , hierarchy ):
time = time + 1 #While vertex has just been discovered
...
这创建了一个名为 time 的本地，它指向与输入时间相同的 int。然后将其递增，现在 time 指向该函数的本地新整数。然后，当你这样做时:
depthFirstSearchVisit(digraph,time,adjacent_node[0],discovered,
undiscovered,explored,nodes,hierarchy)
看起来期望子函数在存在时增加时间，然后当它返回时，我传递下来的时间将被修改。但实际上，不会。
Python 变量传递对于其他语言的程序员来说可能有点令人困惑，因为它并不是真正通过引用或值传递，至少在 C++ 风格中不是这样。你有一个名字，它指向一个对象。当您调用函数时，该函数会获得一个新的本地名称，但它指向同一个对象。只要您不重新分配该名称，那么就像按引用传递一样。但是，一旦您重新分配它，您的本地名称现在就指向一个新对象并且不再共享。
正如评论所说，您最好只在顶部和底部调用 time.time() 。
最后补充一点:如果您确实想要整数时间，那么使用 itertools.count 很容易。但它必须是全局性的:
from itertools import count
gtime = count(0)
#Note: Removed time, as it's useless now
def depthFirstSearchVisit(digraph, node,discovered, undiscovered ,
explored , nodes , hierarchy ):
starttime = gtime.next()
# Call some functions...
# ....
# Those also increment global time
endtime = gtime.next()
关于python - 在深度优先搜索有向图的同时跟踪时间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20480455/