Implementación de la Búsqueda en Profundidad en C# usando Lista y Pila
Quiero crear una primera búsqueda de profundidad en la que he tenido un poco de éxito.
Aquí está mi código hasta ahora (Excepto mi constructor, tenga en cuenta que las clases Vértice y Edge solo contienen propiedades, nada importante publicar aquí):
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;
}
Funciona de la manera que todos los vértices son visitados, pero no en el orden correcto.
Aquí hay una comparación de cómo la mía es visitada en comparación con wikipedia:
Parece que la mía se ha dado la vuelta y está comenzando de derecha a izquierda.
¿Sabes qué lo causa? (También cualquier consejo sobre mi implementación sería muy apreciado)
Gracias
EDITAR: Obtuve mi respuesta, pero aún quería mostrar el resultado final del método 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;
}
6 answers
Parece que el mío está dado la vuelta y comienza de derecha a izquierda. ¿Sabes qué lo causa?
Como otros han señalado, está empujando los nodos-a-visit-next en la pila en orden de izquierda a derecha. Eso significa que se saltan de derecha a izquierda, ya que una pila invierte el orden. Los stacks son el último en entrar, el primero en salir.
Puede solucionar el problema haciendo que GetConnectedVertices construya una pila, no una lista. De esta manera los vértices conectados se invierten dos veces, una vez cuando van en la pila devuelta y una vez cuando van en la pila real.
También cualquier consejo sobre mi implementación sería muy apreciado
La implementación funciona, supongo, pero tiene muchos problemas fundamentales. Si se me presentara ese código para su revisión, esto es lo que diría:
En primer lugar, supongamos que desea hacer dos búsquedas en profundidad de esta estructura de datos al mismo tiempo. O porque lo estabas haciendo en múltiples subprocesos, o porque tiene un bucle anidado en el que el bucle interno hace un DFS para un elemento diferente al bucle externo. ¿Qué pasa? Interfieren entre sí porque ambos intentan mutar los campos "State" y "VisitNumber". Es una muy mala idea tener lo que debería ser una operación "limpia "como buscar realmente hacer que su estructura de datos"sucia".
Al hacerlo, también es imposible usar datos inmutables persistentes para representar porciones redundantes de su gráfico.
Además, noto que omites el código que limpia. ¿Cuándo el" Estado " vuelve a su valor original? ¿Qué pasaría si hicieras un segundo DFS? Fallaría inmediatamente ya que la raíz ya está visitada.
Una mejor opción por todas estas razones es mantener el estado "visitado" en su propio objeto, no en cada vértice.
A continuación, ¿por qué todos los objetos de estado son variables privadas de una clase? Este es un algoritmo simple; no hay necesidad de construir un clase para ello. Un algoritmo de búsqueda en profundidad primero debe tomar el gráfico para buscar como un parámetro formal, no como un estado de objeto, y debe mantener su propio estado local según sea necesario en variables locales, no en campos.
A continuación, la abstracción del gráfico es... bueno, no es una abstracción. Son dos listas, una de vértices y otra de aristas. ¿Cómo sabemos que esas dos listas son consistentes? Supongamos que hay vértices que no están en la lista de vértices, pero están en la lista de aristas. ¿Cómo evitar eso? Lo que quieres es una abstracción gráfica. Deje que la implementación de abstracción de gráficos se preocupe por cómo representar bordes y encontrar vecinos.
A continuación, su uso de ForEach es tanto legal como común, pero hace que me duela la cabeza. Es difícil leer tu código y razonar al respecto con todas las lambdas. Tenemos una declaración "foreach" perfectamente buena. Úsalo.
A continuación, está mutando una propiedad "padre", pero no está del todo claro para qué sirve esta propiedad o por qué se está mutando durante un recorrido. Los vértices en un gráfico arbitrario no tienen "padres" a menos que el gráfico sea un árbol, y si el gráfico es un árbol, entonces no hay necesidad de realizar un seguimiento del estado "visitado"; no hay bucles en un árbol. ¿Qué está pasando aquí? Este código es simplemente extraño, y no es necesario realizar un DFS.
A continuación, su método de ayuda llamado GetConnectedVertices es una mentira. No consigue vértices conectados, consigue vértices conectados no-ya-visitados. Métodos cuyos nombres se encuentran son muy confuso.
Finalmente, esto afirma ser una búsqueda de profundidad primero, pero no busca nada! ¿Dónde se está buscando la cosa? ¿Dónde se devuelve el resultado? Esto no es una búsqueda en absoluto, es un recorrido.
Empezar de nuevo. ¿Qué queréis? Un primer recorrido en profundidad de un gráfico dado un vértice inicial. Entonces implementa eso. Comience por definir lo que está atravesando. Grafica. ¿Qué servicio necesita de un gráfico? Una manera de conseguir el conjunto de vértices vecinos:
interface IGraph
{
IEnumerable<Vertex> GetNeighbours(Vertex v);
}
¿Cuál es su método de retorno? Una secuencia de Vértices en profundidad-primer orden. ¿Qué se necesita? Un vértice inicial. OK:
static class Extensions
{
public static IEnumerable<Vertex> DepthFirstTraversal(
this IGraph graph,
Vertex start)
{ ... }
}
Ahora tenemos una implementación trivial de depth first search; ahora puede usar la cláusula Where:
IGraph myGraph = whatever;
Vertex start = whatever;
Vertex result = myGraph.DepthFirstTraversal(start)
.Where(v=>something)
.FirstOrDefault();
OK, entonces, ¿cómo vamos a implementar ese método para que haga un recorrido sin destruir el estado del gráfico? Mantenga su propio estado externo:
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);
}
}
¿Ves cuánto más limpio y corto es eso? No mutación de estado. Sin perder el tiempo con listas de bordes. No hay funciones auxiliares mal nombradas. Y el código realmente hace lo que dice que hace: atraviesa un gráfico.
También obtenemos los beneficios de los bloques iteradores; es decir, si alguien está usando esto para una búsqueda DF, entonces la iteración se abandona cuando se cumplen los criterios de búsqueda. No tenemos que hacer un recorrido completo si encontramos el resultado temprano.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-01-20 23:08:58
Generalicé el código de @ Eric para el recorrido DFS para cualquier T para hacer que las cosas funcionen para cualquier tipo que tenga hijos-pensé en compartir:
public static IEnumerable<T> DepthFirstTraversal<T>(
T start,
Func<T, IEnumerable<T>> getNeighbours)
{
var visited = new HashSet<T>();
var stack = new Stack<T>();
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);
}
}
}
Ejemplo de uso:
var nodes = DepthFirstTraversal(myNode, n => n.Neighbours);
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-09-21 19:54:01
El problema está en el orden en que busca los elementos. Su for each en StartSearch no garantiza el orden de los elementos. Tampoco tú FindAll en el método GetConnectedVertices. Veamos esta línea:
edges.FindAll(edge => edge.VertexSource == vertex && edge.VertexTarget.State == State.Unvisited).ForEach(edge => vertices.Add(edge.VertexTarget));
Debe agregar un OrderBy() para asegurar el orden deseado.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-04-27 13:35:46
Los elementos se eliminarán de la pila en el orden inverso de la forma en que se empujan sobre ella:
Stach.resultados de push() en: 1 2 3 4 5
Pila.pop() resulta en: 5 4 3 2 1 (así que: de derecha a izquierda)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-04-27 13:36:06
Usted podría disfrutar de esto:
public static bool DepthFirstSearch<T>(this IEnumerable<T> vertices, T rootVertex, T targetVertex, Func<T, IEnumerable<T>> getConnectedVertices, Func<T, T, bool> 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;
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-04-27 14:35:28
Esta es mi implementación, una pila es suficiente. Se realiza un revés antes del bucle foreach.
/// <summary>
/// Depth first search implementation in c#
/// </summary>
/// <typeparam name="T">Type of tree structure item</typeparam>
/// <typeparam name="TChilds">Type of childs collection</typeparam>
/// <param name="node">Starting node to search</param>
/// <param name="ChildsProperty">Property to return child node</param>
/// <param name="Match">Predicate for matching</param>
/// <returns>The instance of matched result, null if not found</returns>
public static T DepthFirstSearch<T, TChilds>(this T node, Func<T, TChilds> ChildsProperty, Predicate<T> Match)
where T:class
{
if (!(ChildsProperty(node) is IEnumerable<T>))
throw new ArgumentException("ChildsProperty must be IEnumerable<T>");
Stack<T> stack = new Stack<T>();
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<T>).Reverse())
stack.Push(child);
}
}
return null;
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-06-18 05:37:00