对深度优先和广度优先进行了注释说明

LMCallMe · LMCallMe · commit 2ae9f8383709 · 2016-11-10T19:04:32.000+08:00
diff --git a/cp16-Template/graph.py b/cp16-Template/graph.py
@@ -1,37 +1,38 @@
 # coding: utf-8
 
-
-def bfs(graph, start, end):
-    path = []
-    visited = [start]
-    while visited:
-        current = visited.pop(0)
-        if current not in path:
-            path.append(current)
-            if current == end:
-                print(path)
+# 算法中的path不是最优的路径，
+# 而是搜索过程中的遍历路径
+def bfs(graph, start, end): # 广度优先图搜索
+    path = [] #　访问路径链
+    visited = [start] # 访问起始城市加入要访问的列表
+    while visited: # 访问城市不为空
+        current = visited.pop(0) # 弹出当前的城市
+        if current not in path: # 如果当前的城市没有在访问路径中
+            path.append(current) # 将当前的城市添加到访问路径中
+            if current == end: # 如果当前的城市是目标城市
+                print(path) # 输出访问路径
                 return (True, path)
-            # 两个顶点不相连，则跳过
-            if current not in graph:
-                continue
-        visited = visited + graph[current]
+            if current not in graph: # 如果当前城市不在图的起点城市中，
+                continue # 则不能作为访问的起点，跳过去
+        # 将当前城市的可访问城市添加到要访问的目标城市列表中
+        visited = visited + graph[current] # 并作为优先访问（在后面优先 pop）的目标城市
     return (False, path)
 
 
-def dfs(graph, start, end):
-    path = []
-    visited = [start]
-    while visited:
-        current = visited.pop(0)
-        if current not in path:
-            path.append(current)
-            if current == end:
-                print(path)
+def dfs(graph, start, end): # 深度优先图搜索
+    path = [] #　访问路径链
+    visited = [start] # 访问起始城市加入要访问的列表
+    while visited: # 访问城市不为空
+        current = visited.pop(0) # 弹出当前的城市
+        if current not in path: # 如果当前的城市没有在访问路径中
+            path.append(current) # 将当前的城市添加到访问路径中
+            if current == end: # 如果当前的城市是目标城市
+                print(path) # 输出访问路径
                 return (True, path)
-            # 两个顶点不相连，则跳过
-            if current not in graph:
-                continue
-        visited = graph[current] + visited
+            if current not in graph: # 如果当前城市不在图的起点城市中，
+                continue # 则不能作为访问的起点，跳过去
+        # 将当前城市的可访问城市添加到要访问的目标城市列表中
+        visited = graph[current] + visited # 并将当前的访问列表作为优先的目标城市（在后面的先 pop）
     return (False, path)
 
 
