使用 DFS 计算距离
Compute distance using DFS
我在这两种方法之间纠结：
M1：
- 用邻接表表示顶点为P、边为A的图G
- 在 G 上使用 DFS，将距 p 的所有距离存储在数组 d 中；
- 循环检查所有条目。如果某些 d[u] >6，return false 否则为 true
M2:
- 用邻接表表示顶点为P、边为A的图G
- 在 G 上使用 BFS，将距 p 的所有距离存储在数组 d 中；
- 循环检查所有条目。如果某些 d[u] >6，return false 否则为 true
这两种方法都会产生最坏的情况O(|P| + |A|)，因此我认为这两种方法都是对这个问题的正确答案。我选择了 DFS 方法，理由是使用 DFS 你应该能够比使用 BFS 更早地找到自由度 7 的 "outlier"，因为使用 BFS 你必须遍历每个顶点直到每个顶点的度数为 7案例.
显然老师说这是错误的，因为使用DFS，你不能计算距离。我不明白为什么你不能计算距离。我可以用一个数字 n 表示我目前的自由度。从根 p 开始，child 将有 n = 1。现在我将 n 存储在数组 d 中。然后我继续向下遍历，直到找不到 child，而 incrementing n 并将值存储在我的数组 d 中。然后，如果 back-tracking 开始，值 n 将递减，直到我们在堆栈上找到任何已访问节点的未访问 child 节点。如果有一个未访问的child，再次递增，然后递增直到找不到更多的child，递减直到从堆栈中找到下一个未访问的child...
我相信这将是一种使用 DFS 存储距离的方法
简单的深度优先搜索算法不一定会产生无向图中的最短路径。例如，考虑一个简单的三角形图。如果您从一个顶点开始，您将处理其他两个顶点。天真的算法会发现有一个顶点与源的距离等于 1，而第二个顶点与源的距离等于 2。但是，这是不正确的，因为从源到任一顶点的距离实际上是一个。
一种更自然的方法是使用广度优先搜索 (BFS) 算法。可以证明广度优先搜索计算的是最短路径，并且它需要的修改要少得多。
您肯定可以使用深度优先搜索来计算从一个节点到另一个节点的距离，但这不是一种自然的方法。事实上，使用深度优先搜索算法（参见：http://www-student.cse.buffalo.edu/~atri/cse331/support/dfs-bfs/index.html）错误计算距离是很常见的，特别是当底层图有循环时。如果你想这样做，有一些特殊情况你必须处理，但这绝对是可能的。
话虽如此，您描述的深度优先搜索算法似乎并不正确。例如，它会在我上面描述的三角形图上失败。这是真的，因为标准深度优先搜索只访问每个顶点一次，并且在设置距离后您不会再次访问顶点。因此，如果您首先将 "longer path" 带到一个循环中的顶点，您最终会得到一个不正确的距离值。
BFS 和 DFS 都可以完成这项工作：它们都可以将搜索深度限制在 6，并且在遍历结束时它们可以检查是否到达了整个种群。但是有一些重要的区别：
有 BFS
BFS 遍历是我会选择的算法。当 BFS 搜索确定一个人的程度时，它是确定的：不需要对其进行更正。
下面是如何使用 BFS 执行此操作的草图：
visited = set() # empty set
frontier = [] # empty array
visited.add(p) # search starts at person p
frontier.append(p)
for degree in [1, 2, 3, 4, 5, 6]:
nextFrontier = [] # empty array
for person in frontier:
for acquaintance in A[person]:
if acquaintance not in visited:
visited.add(acquaintance)
nextFrontier.append(acquaintance)
frontier = nextFrontier
if size(visited) == size(P): # have we reached the whole population?
return True
# After six rounds we did not reach all people, so...
return False
这假设您可以通过 A[person] 找到给定人员的熟人列表。如果 A 的结构不是邻接表而是成对的列表，那么首先对原始 A 进行一些预处理以创建这样的邻接表。
有 DFS
DFS 算法的缺点是它不一定从最佳路径开始，因此它会发现有些人的度数为 6，而实际上有更短的、未经调查的路径可以提高该度数。这意味着 DFS 算法可能需要重新访问节点甚至部分路径（边）以注册此类改进，并通过访问路径将它们级联到 6 级。甚至可能有几个改进要应用于同一个人。
DFS 算法可能如下所示：
degreeOfPerson = dict() # empty key/value dictionary
for person in P:
degreeOfPerson[person] = 7 # some value greater than 6
function dfs(person, degree):
if degree >= 7:
return # don't lose time for higher degrees than 6.
for acquaintance in A[person]:
if degree < degreeOfPerson[acquaintance]: # improvement?
degreeOfPerson[acquaintance] = degree
dfs(acquaintance, degree+1)
# start DFS
degreeOfPerson[p] = 0
dfs(p, 1)
# Check if all persons got a degree of maximum 6
for person in P:
if degreeOfPerson[person] > 6:
return False
return True
例子
如果图形有三个节点，连接成三角形 a-b-c，起始点为 a，那么这就是序列。缩进意味着（递归）调用 dfs:
degreeOfPerson[a] = 0
a->b: degreeOfPerson[b] = 1
b->c: degreeOfPerson[c] = 2
c->a: # cannot improve degreeOfPerson[a]. Backtrack
c->b: # cannot improve degreeOfPerson[b]. Backtrack
b->a: # cannot improve degreeOfPerson[a]. Backtrack
a->c: degreeOfPerson[c] = 1 # improvement!
c->a: # cannot improve degreeOfPerson[a]. Backtrack
c->b: # cannot improve degreeOfPerson[b]. Backtrack
时间复杂度
DFS 可以访问同一条边的次数不超过我们正在寻找的最大次数——在你的例子中是 6。如果这是一个常数，那么它不会影响时间复杂度。但是，如果要检查的度数是输入值，则 DFS 的时间复杂度变为 O(maxdegree * |E| + |V|).
我在这两种方法之间纠结：
M1：
- 用邻接表表示顶点为P、边为A的图G
- 在 G 上使用 DFS，将距 p 的所有距离存储在数组 d 中；
- 循环检查所有条目。如果某些 d[u] >6，return false 否则为 true
M2:
- 用邻接表表示顶点为P、边为A的图G
- 在 G 上使用 BFS，将距 p 的所有距离存储在数组 d 中；
- 循环检查所有条目。如果某些 d[u] >6，return false 否则为 true
这两种方法都会产生最坏的情况O(|P| + |A|)，因此我认为这两种方法都是对这个问题的正确答案。我选择了 DFS 方法，理由是使用 DFS 你应该能够比使用 BFS 更早地找到自由度 7 的 "outlier"，因为使用 BFS 你必须遍历每个顶点直到每个顶点的度数为 7案例.
显然老师说这是错误的，因为使用DFS，你不能计算距离。我不明白为什么你不能计算距离。我可以用一个数字 n 表示我目前的自由度。从根 p 开始，child 将有 n = 1。现在我将 n 存储在数组 d 中。然后我继续向下遍历，直到找不到 child，而 incrementing n 并将值存储在我的数组 d 中。然后，如果 back-tracking 开始，值 n 将递减，直到我们在堆栈上找到任何已访问节点的未访问 child 节点。如果有一个未访问的child，再次递增，然后递增直到找不到更多的child，递减直到从堆栈中找到下一个未访问的child...
我相信这将是一种使用 DFS 存储距离的方法
简单的深度优先搜索算法不一定会产生无向图中的最短路径。例如，考虑一个简单的三角形图。如果您从一个顶点开始，您将处理其他两个顶点。天真的算法会发现有一个顶点与源的距离等于 1，而第二个顶点与源的距离等于 2。但是，这是不正确的，因为从源到任一顶点的距离实际上是一个。
一种更自然的方法是使用广度优先搜索 (BFS) 算法。可以证明广度优先搜索计算的是最短路径，并且它需要的修改要少得多。
您肯定可以使用深度优先搜索来计算从一个节点到另一个节点的距离，但这不是一种自然的方法。事实上，使用深度优先搜索算法（参见：http://www-student.cse.buffalo.edu/~atri/cse331/support/dfs-bfs/index.html）错误计算距离是很常见的，特别是当底层图有循环时。如果你想这样做，有一些特殊情况你必须处理，但这绝对是可能的。
话虽如此，您描述的深度优先搜索算法似乎并不正确。例如，它会在我上面描述的三角形图上失败。这是真的，因为标准深度优先搜索只访问每个顶点一次，并且在设置距离后您不会再次访问顶点。因此，如果您首先将 "longer path" 带到一个循环中的顶点，您最终会得到一个不正确的距离值。
BFS 和 DFS 都可以完成这项工作：它们都可以将搜索深度限制在 6，并且在遍历结束时它们可以检查是否到达了整个种群。但是有一些重要的区别：
有 BFS
BFS 遍历是我会选择的算法。当 BFS 搜索确定一个人的程度时，它是确定的：不需要对其进行更正。
下面是如何使用 BFS 执行此操作的草图：
visited = set() # empty set
frontier = [] # empty array
visited.add(p) # search starts at person p
frontier.append(p)
for degree in [1, 2, 3, 4, 5, 6]:
nextFrontier = [] # empty array
for person in frontier:
for acquaintance in A[person]:
if acquaintance not in visited:
visited.add(acquaintance)
nextFrontier.append(acquaintance)
frontier = nextFrontier
if size(visited) == size(P): # have we reached the whole population?
return True
# After six rounds we did not reach all people, so...
return False
这假设您可以通过 A[person] 找到给定人员的熟人列表。如果 A 的结构不是邻接表而是成对的列表，那么首先对原始 A 进行一些预处理以创建这样的邻接表。
有 DFS
DFS 算法的缺点是它不一定从最佳路径开始，因此它会发现有些人的度数为 6，而实际上有更短的、未经调查的路径可以提高该度数。这意味着 DFS 算法可能需要重新访问节点甚至部分路径（边）以注册此类改进，并通过访问路径将它们级联到 6 级。甚至可能有几个改进要应用于同一个人。
DFS 算法可能如下所示：
degreeOfPerson = dict() # empty key/value dictionary
for person in P:
degreeOfPerson[person] = 7 # some value greater than 6
function dfs(person, degree):
if degree >= 7:
return # don't lose time for higher degrees than 6.
for acquaintance in A[person]:
if degree < degreeOfPerson[acquaintance]: # improvement?
degreeOfPerson[acquaintance] = degree
dfs(acquaintance, degree+1)
# start DFS
degreeOfPerson[p] = 0
dfs(p, 1)
# Check if all persons got a degree of maximum 6
for person in P:
if degreeOfPerson[person] > 6:
return False
return True
例子
如果图形有三个节点，连接成三角形 a-b-c，起始点为 a，那么这就是序列。缩进意味着（递归）调用 dfs:
degreeOfPerson[a] = 0
a->b: degreeOfPerson[b] = 1
b->c: degreeOfPerson[c] = 2
c->a: # cannot improve degreeOfPerson[a]. Backtrack
c->b: # cannot improve degreeOfPerson[b]. Backtrack
b->a: # cannot improve degreeOfPerson[a]. Backtrack
a->c: degreeOfPerson[c] = 1 # improvement!
c->a: # cannot improve degreeOfPerson[a]. Backtrack
c->b: # cannot improve degreeOfPerson[b]. Backtrack
时间复杂度
DFS 可以访问同一条边的次数不超过我们正在寻找的最大次数——在你的例子中是 6。如果这是一个常数，那么它不会影响时间复杂度。但是，如果要检查的度数是输入值，则 DFS 的时间复杂度变为 O(maxdegree * |E| + |V|).