gpt4 book ai didi

c# - 使用列表和堆栈在C#中实现深度优先搜索

转载 作者:IT王子 更新时间:2023-10-29 04:14:01 24 4
gpt4 key购买 nike

我想创建一个深度优先的搜索,该搜索已经取得了一定的成功。

到目前为止,这是我的代码(除我的构造函数外,请注意Vertex和Edge类仅包含属性,在此处没有重要内容可发布):

private Stack<Vertex> workerStack = new Stack<Vertex>();
private List<Vertex> vertices = new List<Vertex>();
private List<Edge> edges = new List<Edge>();

private int numberOfVertices;
private int numberOfClosedVertices;
private int visitNumber = 1;

private void StartSearch()
{
// Make sure to visit all vertices
while (numberOfClosedVertices < numberOfVertices && workerStack.Count > 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<Vertex> GetConnectedVertices(Vertex vertex)
{
List<Vertex> vertices = new List<Vertex>();

// 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<Vertex> GetConnectedVertices(Vertex vertex)
{
List<Vertex> connectingVertices = new List<Vertex>();

(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;
}

最佳答案

It seems mine is turned around and is beginning from right to left. Do you know what causes it?



就像其他人指出的那样,您正在按从左到右的顺序将节点上的访问节点下推。这意味着它们会从右到左弹出,因为堆栈会颠倒顺序。堆栈是后进先出的。

您可以通过使GetConnectedVertices生成堆栈而不是列表来解决此问题。这样,连接的顶点将反转两次,一次是在返回的堆栈上,一次是在实际堆栈上。

Also any advice on my implementation would be greatly appreciated



我想该实现有效,但是它有很多基本问题。如果我收到要检查的代码,这就是我要说的:

首先,假设您想同时对该数据结构进行两次深度优先搜索。可能是因为您正在多个线程上执行此操作,或者是因为您有一个嵌套循环,其中,内部循环为不同于外部循环的元素执行DFS。怎么了?它们彼此干扰,因为它们都试图使“State”和“VisitNumber”字段发生突变。进行应为“干净”的操作(例如搜索实际上会使您的数据结构“脏”)是一个非常糟糕的主意。

这样做还使您无法使用永久不变数据来表示图形的冗余部分。

另外,我注意到您省略了清理代码。 “状态”何时恢复为原始值?如果您做了第二个DFS怎么办?由于已经访问过根,因此它将立即失败。

由于所有这些原因,更好的选择是将“已访问”状态保留在其自己的对象中,而不是在每个顶点中。

接下来,为什么所有状态对象都是类的私有(private)变量?这是一个简单的算法;无需为此构建整个类。深度优先搜索算法应将图搜索作为形式参数而不是对象状态,并且应根据需要在局部变量(而不是字段)中保持自己的局部状态。

接下来,图的抽象是...好吧,它不是抽象。它是两个列表,一个是顶点,另一个是边。我们怎么知道这两个列表是一致的?假设有些顶点不在顶点列表中,但在边列表中。您如何预防呢?您想要的是图形抽象。让图抽象实现担心如何表示边并找到邻居。

其次,您对ForEach的使用既合法又普遍,但这会让我头疼。很难用所有的lambda读取代码和原因。我们有一个非常好的“foreach”语句。用它。

接下来,您要对“父”属性进行变异,但根本不清楚该属性的作用或遍历过程中为何对其进行变异。除非该图是一棵树,否则任意图中的顶点都没有“父级”,如果该图是一棵树,则无需跟踪“已访问”状态;一棵树上没有循环。这里发生了什么?这段代码很奇怪,不需要执行DFS。

接下来,名为GetConnectedVertices的帮助程序方法是一个谎言。它不会获得连接的顶点,而会获得尚未访问的顶点。名称说谎的方法非常令人困惑。

最后,这声称是深度优先搜索,但它不搜索任何内容!在哪里寻找东西?结果返回哪里?这根本不是搜索,而是遍历。

重来。你想要什么? 给定起始顶点,图的深度优先遍历。然后实现。首先定义要遍历的内容。图。您需要从图表中获得什么服务?一种获取相邻顶点集的方法:
interface IGraph
{
IEnumerable<Vertex> GetNeighbours(Vertex v);
}

您返回的方法是什么?深度优先的一系列顶点。需要做些什么?起始顶点。好的:
static class Extensions
{
public static IEnumerable<Vertex> 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<Vertex> DepthFirstTraversal(
this IGraph graph,
Vertex start)
{
var visited = new HashSet<Vertex>();
var stack = new Stack<Vertex>();

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搜索,则在满足搜索条件时将放弃迭代。如果我们尽早发现结果,就不必进行遍历。

关于c# - 使用列表和堆栈在C#中实现深度优先搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5804844/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com