算法小考，小伙伴们来试试吧

超人毛

才发现注册了一年多，处女贴在这里。。。。看来以后要常上来逛逛了。。。

q1208c

回复 7# cj4777

1. 
   
2.     test = {8: ',3,4,5,6,7,9,13,15,',
   
3.                9: ',6,7,10',
   
4.                3: ',2,16,21',
   
5.                21: ',8,9,11,14'}
   
6. 
   
7. test[8] = ',3,4,5,6,7,9,13,15,'
   
8. test[9] = ',6,7,10'
   
9. test[3] = ',2,16,21'
   
10. test[21] = ',8,9,11,14'
    

复制代码

1. 
   
2. for xx in test:
   
3.     if test.get(test[xx]):
   
4.         print xx, test[xx], test[test[xx]]
   

复制代码

随便写的, 我没测试过.

Hadron74

回复 1# cj4777


这个问题，从图论角度出发，就是“如何在有向图中寻找环”的问题：一个字典是一个点的有向边的集合，输出的循环就是有向图的“环”，所以问题就是”how to detect circles in a directed graph?”

问题如果这样描述，算法就不难找了：
从网上搜了两个网页：
中文：
http://www.360doc.com/content/10/0518/16/1304528_28243924.shtml
英文：
http://stackoverflow.com/questio ... in-a-directed-graph

比较忙，python代码就不写了。期待大侠前来。。。

icymirror

回复 13# Hadron74

今天空，练下手。

1. """
   
2. To check whether there is cycle in a graph(Direction based),
   
3. have to perform deep first search based navigation.
   
4. If there is a node appeared more than 1 times in path,
   
5. then, the path is a cycle.
   
6. 
   
7. Direction Graps is stored with following style:
   
8.     { Node1: [NodeName1, NodeName2],
   
9.       Node2: [NodeName1, NodeName2]}
   
10. In the format, Node1, Node2 are represent related nodes in graph.
    
11. And [NodeName, NodeName2] represent relate curve from curent node to next node.
    
12. """
    
13. 
    
14. from copy import deepcopy
    
15. 
    
16. def dfs(node, graph, path):
    
17.     '''Deep first search navigation, if node appeared in path, cycle found.'''
    
18.     # if could find node
    
19.     if graph.has_key(node):
    
20.         # If node in navigation path, find cycle, return result and path
    
21.         if node in path:
    
22.             return path
    
23.         # If could not find node in path, for each sub-arc, recursive dfs
    
24.         else:
    
25.             for arc in graph[node]:
    
26.                 # deepcopy is required, avoid dfs pollute tracking
    
27.                 newpath = deepcopy(path)
    
28.                 newpath.add(node)
    
29.                 result = dfs(arc, graph, newpath)
    
30.                 if result:
    
31.                     return result
    
32.     else:
    
33.         # If could not find coming node, navigation end, navigation back
    
34.         return None
    
35. 
    
36. def main():
    
37.     testData = {8: [3,4,5,6,7,9,13,15],
    
38.                9: [6,7,10],
    
39.                3: [2,16,21],
    
40.                21: [8,9,11,14]}
    
41.     path = set()
    
42.     for node in testData.iterkeys():
    
43.         result = dfs(node, testData, path)
    
44.         if result:
    
45.             print result
    
46.             break;

复制代码