Cycle from a given node
题目
Write a predicate cycle(G, A, P) to find a closed path (cycle) P starting at a given node A in the graph G. The predicate should return all cycles via backtracking.
解题思路
环路其是就是起始点和目的点是同一个点的点到点的路径。所以可以重用P602中的返法罗列所有环路。
- 从一点出发，罗列所有相邻点
- 如果相邻点为起始点，则已找到一个环路
- 如果相邻点已在路径中且不是起始点，则忽略
- 其它相邻点可以作为路径中下一个点的候选
- 以每一个候选相邻点被出发点，套用步骤1和2
举个例子，给定如下图，求从点a到点a的所有环路。
- 初始路径
[a] - 从点
a出发，有相邻点b, db不在路径中且不是起始点，将其加入路径。从b出发，有相邻点c, ec不在路径[a, b]中且不是起始点，将其加入路径。从c出发，有相邻点b, eb已在路径[a, b, c]中，略过e不在路径[a, b, c]中且不是起始点，将其加入路径。从e出发，有相邻点b, c, d, hb已在路径中c已在路径中d不在路径中且不是起始点，加入路径。从d出发，有相邻点a, e, g, fa是起始点，找到一条环路[a, b, c, e, d, a]- ...
- ...
- ...
代码实现：
def cycle(g, start):
cycles = listPath(g, [start], start, start)
return [[start] + e for e in cycles]
def listPath(g, path, current, end):
# it reach destination when current node is end one
if current == end and len(path) > 1:
return [[]]
nodes = nextNodes(g, path, current)
return [[nextNode]+remainPath
for nextNode in nodes
for remainPath in listPath(g, path+[nextNode], nextNode, end)]
def nextNodes(g, path, start):
for edge in g[1]:
if edge[0] == start and edge[1] not in path[1:]:
yield edge[1]
elif edge[1] == start and edge[0] not in path[1:]:
yield edge[0]