chen0040 /
pyalgs
| Total Complexity | 7 |
| Total Lines | 23 |
| Duplicated Lines | 0 % |
| Changes | 1 | ||
| Bugs | 0 | Features | 0 |
| 1 | from pyalgs.data_structures.commons.stack import Stack |
||
| 4 | class DepthFirstOrder(object): |
||
| 5 | |||
| 6 | marked = None |
||
| 7 | reversePostOrder = None |
||
| 8 | |||
| 9 | def __init__(self, G): |
||
| 10 | self.reversePostOrder = Stack.create() |
||
| 11 | vertex_count = G.vertex_count() |
||
| 12 | self.marked = [False] * vertex_count |
||
| 13 | |||
| 14 | for v in range(vertex_count): |
||
| 15 | if not self.marked[v]: |
||
| 16 | self.dfs(G, v) |
||
| 17 | |||
| 18 | def dfs(self, G, v): |
||
| 19 | self.marked[v] = True |
||
| 20 | for w in G.adj(v): |
||
| 21 | if not self.marked[w]: |
||
| 22 | self.dfs(G, w) |
||
| 23 | self.reversePostOrder.push(v) |
||
| 24 | |||
| 25 | def postOrder(self): |
||
| 26 | return self.reversePostOrder.iterate() |
