如何用改进的DFS算法遍历循环有向图-Java 学习之路

OVERVIEW

我试图弄清楚如何使用某种DFS迭代算法遍历 directed cyclic graphs . 这里's a little mcve version of what I currently got implemented (it doesn'吨处理周期）：

class Node(object):

    def __init__(self, name):
        self.name = name

    def start(self):
        print '{}_start'.format(self)

    def middle(self):
        print '{}_middle'.format(self)

    def end(self):
        print '{}_end'.format(self)

    def __str__(self):
        return "{0}".format(self.name)


class NodeRepeat(Node):

    def __init__(self, name, num_repeats=1):
        super(NodeRepeat, self).__init__(name)
        self.num_repeats = num_repeats


def dfs(graph, start):
    """Traverse graph from start node using DFS with reversed childs"""

    visited = {}
    stack = [(start, "")]
    while stack:
        # To convert dfs -> bfs
        # a) rename stack to queue
        # b) pop becomes pop(0)
        node, parent = stack.pop()
        if parent is None:
            if visited[node] < 3:
                node.end()
            visited[node] = 3
        elif node not in visited:
            if visited.get(parent) == 2:
                parent.middle()
            elif visited.get(parent) == 1:
                visited[parent] = 2

            node.start()
            visited[node] = 1

            stack.append((node, None))

            # Maybe you want a different order, if it's so, don't use reversed
            childs = reversed(graph.get(node, []))
            for child in childs:
                if child not in visited:
                    stack.append((child, node))


if __name__ == "__main__":
    Sequence1 = Node('Sequence1')
    MtxPushPop1 = Node('MtxPushPop1')
    Rotate1 = Node('Rotate1')
    Repeat1 = NodeRepeat('Repeat1', num_repeats=2)

    Sequence2 = Node('Sequence2')
    MtxPushPop2 = Node('MtxPushPop2')
    Translate = Node('Translate')
    Rotate2 = Node('Rotate2')
    Rotate3 = Node('Rotate3')
    Scale = Node('Scale')
    Repeat2 = NodeRepeat('Repeat2', num_repeats=3)
    Mesh = Node('Mesh')

    cyclic_graph = {
        Sequence1: [MtxPushPop1, Rotate1],
        MtxPushPop1: [Sequence2],
        Rotate1: [Repeat1],
        Sequence2: [MtxPushPop2, Translate],
        Repeat1: [Sequence1],
        MtxPushPop2: [Rotate2],
        Translate: [Rotate3],
        Rotate2: [Scale],
        Rotate3: [Repeat2],
        Scale: [Mesh],
        Repeat2: [Sequence2]
    }

    dfs(cyclic_graph, Sequence1)

    print '-'*80

    a = Node('a')
    b = Node('b')
    dfs({
        a : [b],
        b : [a]
    }, a)

上面的代码测试了几个案例，第一个是下图的某种表示：

enter image description here

第二个是最简单的一个图形包含一个"infinite"循环 {a->b, b->a}

REQUIREMENTS

当找到一个"infinite cycle"时，有人说't exist such a thing like 2678232 , let' s会有一个最大阈值（全局变量）来指示何时停止循环"pseudo-infinite cycles"
所有图形节点都能够创建循环但是会存在一个名为 Repeat 的特殊节点，您可以在其中指示循环循环的循环次数
我发布的上述mcve是遍历算法的迭代版本 doesn't know how to deal with cyclic graphs . 理想情况下，解决方案也是迭代的，但如果存在更好的递归解决方案，那就太好了
数据结构我们被称为"directed acyclic graphs"，因为在这种情况下， each node has its children ordered ，并且在图中节点连接没有顺序 .
一切都可以连接到编辑器中的任何内容 . 您将能够执行任何块组合，唯一的限制是执行计数器，如果您进行了无限循环或过多的迭代，它将会溢出 .
算法将保留开始/中间/后节点的方法执行，类似于上面的代码片段

QUESTION

任何人都可以提供某种知道如何遍历无限/有限循环的解决方案吗？

REFERENCES

如果此时问题尚不清楚，你可以在这个问题上阅读更多关于这个问题，整个想法将使用遍历算法来实现类似于该文章中所示的类似工具 .

这是一个屏幕截图，显示了这种数据结构的全部功能我想弄清楚如何遍历和运行：

enter image description here

2 回答

在我开始之前，我也希望这些评论能够详细阐述我的成就 . 如果您需要更多解释，请查看我对代码下面的递归方法的解释 .

# If you don't want global variables, remove the indentation procedures
indent = -1

MAX_THRESHOLD = 10
INF = 1 << 63

def whitespace():
    global indent
    return '|  ' * (indent)

class Node:
    def __init__(self, name, num_repeats=INF):
        self.name = name
        self.num_repeats = num_repeats

    def start(self):
        global indent
        if self.name.find('Sequence') != -1:
            print whitespace()
            indent += 1
        print whitespace() + '%s_start' % self.name

    def middle(self):
        print whitespace() + '%s_middle' % self.name

    def end(self):
        global indent
        print whitespace() + '%s_end' % self.name
        if self.name.find('Sequence') != -1:
            indent -= 1
            print whitespace()

def dfs(graph, start):
    visits = {}
    frontier = [] # The stack that keeps track of nodes to visit

    # Whenever we "visit" a node, increase its visit count
    frontier.append((start, start.num_repeats))
    visits[start] = visits.get(start, 0) + 1

    while frontier:
        # parent_repeat_count usually contains vertex.repeat_count
        # But, it may contain a higher value if a repeat node is its ancestor
        vertex, parent_repeat_count = frontier.pop()

        # Special case which signifies the end
        if parent_repeat_count == -1:
            vertex.end()
            # We're done with this vertex, clear visits so that 
            # if any other node calls us, we're still able to be called
            visits[vertex] = 0
            continue

        # Special case which signifies the middle
        if parent_repeat_count == -2:
            vertex.middle()
            continue  

        # Send the start message
        vertex.start()

        # Add the node's end state to the stack first
        # So that it is executed last
        frontier.append((vertex, -1))

        # No more children, continue
        # Because of the above line, the end method will
        # still be executed
        if vertex not in graph:
            continue

        ## Uncomment the following line if you want to go left to right neighbor
        #### graph[vertex].reverse()

        for i, neighbor in enumerate(graph[vertex]):
            # The repeat count should propagate amongst neighbors
            # That is if the parent had a higher repeat count, use that instead
            repeat_count = max(1, parent_repeat_count)
            if neighbor.num_repeats != INF:
                repeat_count = neighbor.num_repeats

            # We've gone through at least one neighbor node
            # Append this vertex's middle state to the stack
            if i >= 1:
                frontier.append((vertex, -2))

            # If we've not visited the neighbor more times than we have to, visit it
            if visits.get(neighbor, 0) < MAX_THRESHOLD and visits.get(neighbor, 0) < repeat_count:
                frontier.append((neighbor, repeat_count))
                visits[neighbor] = visits.get(neighbor, 0) + 1

def dfs_rec(graph, node, parent_repeat_count=INF, visits={}):
    visits[node] = visits.get(node, 0) + 1

    node.start()

    if node not in graph:
        node.end()
        return

    for i, neighbor in enumerate(graph[node][::-1]):
        repeat_count = max(1, parent_repeat_count)
        if neighbor.num_repeats != INF:
            repeat_count = neighbor.num_repeats

        if i >= 1:
            node.middle()

        if visits.get(neighbor, 0) < MAX_THRESHOLD and visits.get(neighbor, 0) < repeat_count:
            dfs_rec(graph, neighbor, repeat_count, visits)

    node.end()  
    visits[node] = 0

Sequence1 = Node('Sequence1')
MtxPushPop1 = Node('MtxPushPop1')
Rotate1 = Node('Rotate1')
Repeat1 = Node('Repeat1', 2)

Sequence2 = Node('Sequence2')
MtxPushPop2 = Node('MtxPushPop2')
Translate = Node('Translate')
Rotate2 = Node('Rotate2')
Rotate3 = Node('Rotate3')
Scale = Node('Scale')
Repeat2 = Node('Repeat2', 3)
Mesh = Node('Mesh')

cyclic_graph = {
        Sequence1: [MtxPushPop1, Rotate1],
        MtxPushPop1: [Sequence2],
        Rotate1: [Repeat1],
        Sequence2: [MtxPushPop2, Translate],
        Repeat1: [Sequence1],
        MtxPushPop2: [Rotate2],
        Translate: [Rotate3],
        Rotate2: [Scale],
        Rotate3: [Repeat2],
        Scale: [Mesh],
        Repeat2: [Sequence2]
    }

dfs(cyclic_graph, Sequence1)

print '-'*40

dfs_rec(cyclic_graph, Sequence1)

print '-'*40

dfs({Sequence1: [Translate], Translate: [Sequence1]}, Sequence1)

print '-'*40

dfs_rec({Sequence1: [Translate], Translate: [Sequence1]}, Sequence1)

输入和（格式正确和缩进）输出可以找到here . 如果你想看看我如何格式化输出，请参考代码，也可以是found on CodeSkulptor .

对，解释 . 更容易理解但更低效的递归解决方案，我将用它来帮助解释，如下：

def dfs_rec(graph, node, parent_repeat_count=INF, visits={}):
    visits[node] = visits.get(node, 0) + 1

    node.start()

    if node not in graph:
        node.end()
        return

    for i, neighbor in enumerate(graph[node][::-1]):
        repeat_count = max(1, parent_repeat_count)
        if neighbor.num_repeats != INF:
            repeat_count = neighbor.num_repeats

        if i >= 1:
            node.middle()

        if visits.get(neighbor, 0) < MAX_THRESHOLD and visits.get(neighbor, 0) < repeat_count:
            dfs_rec(graph, neighbor, repeat_count, visits)

    node.end()  
    visits[node] = 0

我们要做的第一件事是访问节点 . 我们通过增加字典中节点的访问次数来完成此操作 .
然后我们引发节点的 start 事件 .
我们做一个简单的检查，看看节点是否是无子（叶）节点 . 如果是，我们举起 end 事件并返回 .
现在我们已经确定节点有邻居，我们遍历每个邻居 . Side Note: 我在递归版本中反转邻居列表（通过使用 graph[node][::-1] ）以维持邻居遍历的相同顺序（从右到左），如在迭代版本中那样 .
对于每个邻居，我们首先计算重复计数 . 重复计数从祖先节点传播（继承），因此除非邻居包含重复计数值，否则将使用继承的重复计数 .
如果正在处理第二个（或更高）邻居，则引发当前节点的 middle 事件（ not 邻居） .
如果可以访问邻居，则访问邻居 . 可访问性检查是通过检查邻居是否被访问的次数小于a） MAX_THRESHOLD 次（对于伪无限循环）和b）上述计算的重复计数次数来完成的 .
我们现在已经完成了这个节点;提升 end 事件并清除其在哈希表中的访问 . 这样做是为了如果某个其他节点再次调用它，则它不会使可访问性检查失败和/或执行少于所需的次数 .

回复于 2024-04-29T11:54:09+08:00

7
根据comment66244567 - 通过忽略到访问节点的链接并执行广度优先搜索将图形缩减为树，因为这将生成更自然（并且可能更 balancer ）的树：
```
def traverse(graph,node,process):
    seen={node}
    current_level=[node]
    while current_level:
        next_level=[]
        for node in current_level:
            process(node)
            for child in (link for link in graph.get(node,[]) if link not in seen):
                next_level.append(child)
                seen.add(child)
        current_level=next_level
```
使用您的图表和 def process(node): print node ，这会产生：
```
In [24]: traverse(cyclic_graph,Sequence1,process)
Sequence1
MtxPushPop1
Rotate1
Sequence2
Repeat1
MtxPushPop2
Translate
Rotate2
Rotate3
Scale
Repeat2
Mesh
```
另一个BFS算法iterative deepening DFS（以速度为代价使用更少的内存）在这种情况下不会赢得任何东西：因为你必须存储对被访问的引用节点，你已经消耗了O（n）内存 . 你不需要产生中间结果（但无论如何你都可以 - 例如 yield 处理一个级别后的东西） .
回复于 2024-04-29T11:54:09+08:00

如何用改进的DFS算法遍历循环有向图

2 回答

相关问题