遍历反向图问题即在有向图中按照反向边进行遍历。可通过以下步骤实现:
下面是Python代码实现:
from collections import defaultdict
class Graph:
def __init__(self, vertices):
self.graph = defaultdict(list)
self.V = vertices
def addEdge(self, u, v):
self.graph[u].append(v)
def DFSUtil(self, v, visited, stack):
visited[v] = True
for i in self.graph[v]:
if not visited[i]:
self.DFSUtil(i, visited, stack)
stack.append(v)
def getReverse(self):
g = Graph(self.V)
for i in self.graph:
for j in self.graph[i]:
g.addEdge(j, i)
return g
def printGraph(self):
for i in self.graph:
print(i, " -> ", " -> ".join(map(str, self.graph[i])))
def reverseTraversal(self, s):
visited = [False]*self.V
stack = []
# 获取反向图
g = self.getReverse()
# 遍历反向图
g.DFSUtil(s, visited, stack)
# 获取遍历序列
res = []
while stack:
res.append(stack.pop())
# 根据遍历序列反向获取路径
ans = []
visited = [False]*self.V
for i in range(len(res)):
if not visited[res[i]]:
self.getDfs(res[i], visited, ans)
return ans
def getDfs(self, v, visited, ans):
visited[v] = True
ans.append(v)
for i in self.graph[v]:
if not visited[i]:
self.getDfs(i, visited, ans)
g