使用List和Stack实现深度优先搜索到C＃
我想创建一个深度优先搜索，我已经有点成功了。
这是我到目前为止的代码（除了我的构造函数，请注意Vertex和Edge类只包含属性，这里没有重要的内容）：
private Stack workerStack = new Stack(); private List vertices = new List(); private List edges = new List(); private int numberOfVertices; private int numberOfClosedVertices; private int visitNumber = 1; private void StartSearch() { // Make sure to visit all vertices while (numberOfClosedVertices 0) { // Get top element in stack and mark it as visited Vertex workingVertex = workerStack.Pop(); workingVertex.State = State.Visited; workingVertex.VisitNumber = visitNumber; visitNumber++; numberOfClosedVertices++; // Get all edges connected to the working vertex foreach (Vertex vertex in GetConnectedVertices(workingVertex)) { vertex.Parent = workingVertex; workerStack.Push(vertex); } } } private List GetConnectedVertices(Vertex vertex) { List vertices = new List(); // Get all vertices connected to vertex and is unvisited, then add them to the vertices list edges.FindAll(edge => edge.VertexSource == vertex && edge.VertexTarget.State == State.Unvisited).ForEach(edge => vertices.Add(edge.VertexTarget)); return vertices; } 它的工作方式是访问所有顶点，但顺序不正确。
以下是与维基百科相比我的访问方式的比较： 
似乎我的转身，从右到左开始。
你知道是什么原因引起的吗？ （对我的实施的任何建议将不胜感激）
谢谢
编辑：我得到了答案，但仍希望显示GetConnectedVertices方法的最终结果：
private List GetConnectedVertices(Vertex vertex) { List connectingVertices = new List(); (from edge in edges where edge.VertexSource == vertex && edge.VertexTarget.State == State.Unvisited select edge). Reverse(). ToList(). ForEach(edge => connectingVertices.Add(edge.VertexTarget)); return connectingVertices; }
似乎我的转身并从右到左开始。 你知道是什么原因引起的吗？
正如其他人所指出的那样，您正在按顺序从左到右推送堆栈中的节点到访问次。 这意味着它们会从右向左弹出，因为堆栈会颠倒顺序。 堆栈是后进先出的。
您可以通过使GetConnectedVertices构建堆栈而不是列表来解决问题。 这样，连接的顶点反转两次 ，一次当它们返回到返回的堆栈时，一次当它们进入实际堆栈时。
对我的实施的任何建议将不胜感激
我认为实施工作有效，但它有很多基本问题。 如果我被提交给审查代码，这就是我要说的：
首先，假设您希望同时对此数据结构进行两次深度优先搜索。 要么是因为你在多个线程上执行它，要么是因为你有一个嵌套循环，其中内部循环为外部循环执行不同元素的DFS。 怎么了？ 它们相互干扰，因为它们都试图改变“State”和“VisitNumber”字段。 这应该是一个“干净”的操作，如搜索实际上使您的数据结构“脏”，这是一个非常糟糕的主意。
这样做也使您无法使用持久不可变数据来表示图形的冗余部分。
另外，我注意到你省略了清理的代码。 “状态”什么时候回到原来的价值？ 如果你做了第二次 DFS怎么办？ 它会立即失败，因为已经访问了root。
出于所有这些原因，更好的选择是将“访问”状态保持在其自己的对象中，而不是在每个顶点中。
接下来，为什么所有状态对象都是类的私有变量？ 这是一个简单的算法; 没有必要为它构建一个完整的类。 深度优先搜索算法应该将图形作为forms参数进行搜索，而不是作为对象状态，并且它应该在局部变量而不是字段中根据需要保持其自己的本地状态。
接下来，图的抽象是……好吧，它不是抽象。 它是两个列表，一个是顶点，另一个是边。 我们怎么知道这两个列表是否一致？ 假设有些顶点不在顶点列表中但位于边缘列表中。 你怎么防止这种情况？ 你想要的是图形抽象。 让图形抽象实现担心如何表示边缘和查找邻居。
接下来，你对ForEach的使用既合法又常见，但它让我头疼。 很难用所有的lambdas读取你的代码和理由。 我们有一个非常好的“foreach”声明。 用它。
接下来，您正在改变“父”属性，但它根本不清楚这个属性是什么或为什么它在遍历期间被突变。 任意图中的顶点没有“父”，除非图是树，如果图是树，则不需要跟踪“访问”状态; 树中没有循环。 这里发生了什么？ 这段代码很奇怪，没有必要执行DFS。
接下来，名为GetConnectedVertices的辅助方法是一个谎言。 它没有连接顶点，它连接了未经访问过的顶点。 名字所在的方法非常混乱。
最后，这声称是深度优先搜索，但它不搜索任何东西！ 被搜索的东西在哪里？ 返回结果在哪里？ 这根本不是搜索，而是遍历。
重来。 你想要什么？ 给定起始顶点的图的深度优先遍历 。 然后执行。 首先定义您要遍历的内容。 图表。 您需要从图表中获得哪些服务？ 获取相邻顶点集的方法：
interface IGraph { IEnumerable GetNeighbours(Vertex v); }
你的方法回归了什么？ 一系列顶点深度优先顺序。 需要做些什么？ 一个起始顶点。 好：
static class Extensions { public static IEnumerable DepthFirstTraversal( this IGraph graph, Vertex start) { ... } }
我们现在有一个简单的深度优先搜索实现; 你现在可以使用Where子句：
IGraph myGraph = whatever; Vertex start = whatever; Vertex result = myGraph.DepthFirstTraversal(start) .Where(v=>something) .FirstOrDefault();
好的，那么我们如何实现该方法，以便在不破坏图形状态的情况下进行遍历？ 保持自己的外部状态：
public static IEnumerable DepthFirstTraversal( this IGraph graph, Vertex start) { var visited = new HashSet (); var stack = new Stack (); stack.Push(start); while(stack.Count != 0) { var current = stack.Pop(); if(!visited.Add(current)) continue; yield return current; var neighbours = graph.GetNeighbours(current) .Where(n=>!visited.Contains(n)); // If you don't care about the left-to-right order, remove the Reverse foreach(var neighbour in neighbours.Reverse()) stack.Push(neighbour); } }
看看有多清洁和短暂？ 没有状态的突变。 没有边缘清单。 没有错误命名的辅助函数。 代码实际上做了它所说的：遍历图形。
我们也获得了迭代器块的好处; 即，如果有人将其用于DF搜索，则在满足搜索条件时放弃迭代。 如果我们尽早找到结果，我们不必进行完整的遍历。
我概括了@ Eric的任何T DFS遍历代码，使得任何有孩子的类型的东西都适用 – 我想我会分享：
public static IEnumerable DepthFirstTraversal ( T start, Func> getNeighbours) { var visited = new HashSet (); var stack = new Stack (); stack.Push(start); while (stack.Count != 0) { var current = stack.Pop(); visited.Add(current); yield return current; var neighbours = getNeighbours(current).Where(node => !visited.Contains(node)); // If you don't care about the left-to-right order, remove the Reverse foreach(var neighbour in neighbours.Reverse()) { stack.Push(neighbour); } } }
用法示例：
var nodes = DepthFirstTraversal(myNode, n => n.Neighbours);
问题在于您搜索元素的顺序。 您在StartSearch中的for each都不保证元素顺序。 您在GetConnectedVertices方法中也没有FindAll 。 我们来看看这一行：
edges.FindAll(edge => edge.VertexSource == vertex && edge.VertexTarget.State == State.Unvisited).ForEach(edge => vertices.Add(edge.VertexTarget));
您应该添加OrderBy()以确保所需的顺序。
项目将以相反的顺序弹出堆栈，如何按下它们：
stach.push（）结果：1 2 3 4 5
stack.pop（）结果：5 4 3 2 1（所以：从右到左）
你可能会喜欢这个：
public static bool DepthFirstSearch(this IEnumerable vertices, T rootVertex, T targetVertex, Func> getConnectedVertices, Func matchFunction = null) { if (getConnectedVertices == null) { throw new ArgumentNullException("getConnectedVertices"); } if (matchFunction == null) { matchFunction = (t, u) => object.Equals(t, u); } var directlyConnectedVertices = getConnectedVertices(rootVertex); foreach (var vertex in directlyConnectedVertices) { if (matchFunction(vertex, targetVertex)) { return true; } else if (vertices.DepthFirstSearch(vertex, targetVertex, getConnectedVertices, matchFunction)) { return true; } } return false; }
这是我的实现，一个堆栈足够好。 在foreach循环之前完成相反的操作。
/// /// Depth first search implementation in c# /// /// Type of tree structure item /// Type of childs collection /// Starting node to search /// Property to return child node /// Predicate for matching /// The instance of matched result, null if not found public static T DepthFirstSearch(this T node, Func ChildsProperty, Predicate Match) where T:class { if (!(ChildsProperty(node) is IEnumerable )) throw new ArgumentException("ChildsProperty must be IEnumerable "); Stack stack = new Stack (); stack.Push(node); while (stack.Count > 0) { T thisNode = stack.Pop(); #if DEBUG System.Diagnostics.Debug.WriteLine(thisNode.ToString()); #endif if (Match(thisNode)) return thisNode; if (ChildsProperty(thisNode) != null) { foreach (T child in (ChildsProperty(thisNode) as IEnumerable ).Reverse()) stack.Push(child); } } return null; }