Mise en œuvre de la profondeur première recherche dans C# à L'aide de la liste et de la pile
je veux créer une première recherche en profondeur dans laquelle j'ai eu un certain succès.
Voici mon code jusqu'à présent (sauf mon constructeur, notez que les classes Vertex et Edge ne contiennent que des propriétés, rien d'important à signaler ici):
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;
}
son fonctionnement de la façon dont tous les sommets sont visités, mais pas dans le bon ordre.
Voici une comparaison de la façon dont le mien est visité par rapport à wikipedia:
il semble que le mien soit il fait demi-tour et commence de droite à gauche.
savez-vous ce qui en est la cause? (Également des conseils sur ma mise en œuvre serait grandement apprécié)
Merci
EDIT: j'ai eu ma réponse, mais j'ai quand même voulu montrer le résultat final de la méthode 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 réponses
il semble que le mien est retourné et commence de droite à gauche. Savez-vous quelles en sont les causes?
Comme d'autres l'ont noté, vous poussent les nœuds-pour-visiter-le prochain sur la pile dans l'ordre de gauche à droite. Qui signifie qu'ils sont détachés de droite à gauche, depuis une pile inverse l'ordre. Les piles sont les dernières entrées-sorties.
vous pouvez résoudre le problème en faisant construire une pile par GetConnectedVertices, pas une liste. De cette façon, les sommets sont connectés inversé deux fois, une fois quand ils vont sur la pile retournée et une fois quand ils vont sur la pile réelle.
en outre, tout conseil sur ma mise en oeuvre serait grandement apprécié
la mise en oeuvre fonctionne, je suppose, mais elle a beaucoup de problèmes fondamentaux. Si on me présentait ce code pour examen, voici ce que je dirais:
tout d'abord, supposons que vous vouliez faire deux recherches en profondeur de cette structure de données à la même temps. Soit parce que vous le faisiez sur plusieurs threads, soit parce que vous avez une boucle imbriquée dans laquelle la boucle interne fait une DFS pour un élément différent de la boucle externe. Ce qui se passe? Ils interfèrent les uns avec les autres parce que les deux tentent de muter l'état et les champs "VisitNumber". C'est une très mauvaise idée d'avoir ce qui devrait être une opération "propre" comme la recherche qui rend en fait votre structure de données "sale".
ce faisant, il vous est également impossible d'utiliser persistantes les données immuables pour représenter les parties redondantes de votre graphique.
aussi, je remarque que vous omettez le code qui nettoie. Quand l '"État" est-il Revenu à sa valeur originelle? Que faire si vous avez un deuxième DFS? Il échouerait immédiatement puisque la racine est déjà visitée.
Un meilleur choix pour toutes ces raisons, est de garder les "visité" état dans son propre objet, pas à chaque sommet.
Ensuite, pourquoi tous les objets d'état privé les variables d'une classe? C'est un algorithme simple; il n'y a pas besoin de construire une classe entière pour cela. Un algorithme de recherche en profondeur doit prendre le graphe pour rechercher en tant que paramètre formel, pas en tant qu'état de l'objet, et il doit maintenir son propre état local comme nécessaire dans les variables locales, pas les champs.
ensuite, l'abstraction du graphique est... eh bien, ce n'est pas une abstraction. C'est deux listes, une de sommets et une de bords. Comment savons-nous que ces deux listes sont même compatibles? Supposer il y a des vertices qui ne sont pas dans la liste des vertex mais qui sont sur la liste des bordures. Comment empêcher cela? Ce que vous voulez, c'est une abstraction graphique. Laissez l'implémentation de l'abstraction graphique s'inquiéter de la façon de représenter les contours et de trouver des voisins.
ensuite, votre usage de ForEach est à la fois légal et courant, mais cela me fait mal à la tête. Il est difficile de lire votre code et la raison à ce sujet avec tous les lambdas. Nous avons une très bonne "foreach". Utiliser.
ensuite, vous êtes en train de muter une propriété "parent" mais on ne sait pas du tout à quoi sert cette propriété ni pourquoi elle subit une mutation lors d'une traversée. Les sommets dans un graphe arbitraire n'ont pas de "parents" à moins que le graphe ne soit un arbre, et si le graphe est un arbre, alors il n'est pas nécessaire de garder une trace de l'état "visité"; il n'y a pas de boucles dans un arbre. Ce qui se passe ici? Ce code est tout simplement bizarre, et il n'est pas nécessaire d'effectuer une DFS.
ensuite, votre méthode d'aide nommée GetConnectedVertices est un mensonge. Il n' pas obtenir vertices connectés, il obtient vertices connectés pas-déjà-visités. Les méthodes dont les noms se trouvent sont très déroutantes.
enfin, ceci prétend être une première recherche en profondeur mais il ne cherche rien! où se trouve la chose recherchée? Où est le résultat retourné? Ce n'est pas une recherche, c'est une traversée.
recommencer. Que voulez-vous? profondeur d'abord la traversée d'un graphe donné un départ vertex. Puis le mettre en œuvre que. Commençons par définir ce que vous traversez. Graphique. Quel service avez-vous besoin d'un graphique? Une façon d'obtenir l'ensemble des sommets voisins:
interface IGraph
{
IEnumerable<Vertex> GetNeighbours(Vertex v);
}
Quelle est votre méthode de retour? Une séquence de Sommets en profondeur-premier ordre. Que faut-il faire? Un sommet de départ. OK:
static class Extensions
{
public static IEnumerable<Vertex> DepthFirstTraversal(
this IGraph graph,
Vertex start)
{ ... }
}
Nous avons maintenant une banale mise en œuvre de parcours en profondeur d'abord de recherche; vous pouvez maintenant utiliser la clause where:
IGraph myGraph = whatever;
Vertex start = whatever;
Vertex result = myGraph.DepthFirstTraversal(start)
.Where(v=>something)
.FirstOrDefault();
OK, alors comment allons-nous implémenter cette méthode pour qu'elle fait un parcours sans démolition du graphe d'état? Maintenir votre propre extérieure de l'état:
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);
}
}
voyez combien plus propre et plus court c'est? Pas de mutation d'état. Pas de conneries avec des listes de bord. Pas de fonctions d'aide mal nommées. Et le code fait en fait ce qu'il dit qu'il fait: traverse un graphe.
nous obtenons également les avantages des blocs itérateurs; à savoir, si quelqu'un utilise ceci pour une recherche DF, alors l'itération est abandonnée lorsque les critères de recherche sont respectés. Nous ne pas avoir à faire une traversée complète si nous trouvons le résultat tôt.
je généralisée @Eric du code de DFS traversal pour tout T pour faire fonctionner les choses pour tout type qui a des enfants - j'ai pensé que je devais partager:
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);
}
}
}
Exemple d'utilisation:
var nodes = DepthFirstTraversal(myNode, n => n.Neighbours);
le problème est dans l'ordre de recherche des éléments. Votre for eachStartSearch ne garantit pas l'élément de commande. Ni ne vous FindAllGetConnectedVertices méthode. Regardons cette ligne:
edges.FindAll(edge => edge.VertexSource == vertex && edge.VertexTarget.State == State.Unvisited).ForEach(edge => vertices.Add(edge.VertexTarget));
vous devriez ajouter un OrderBy() assurer l'ordre souhaité.
les Articles seront sauté de la pile dans l'ordre inverse de la façon dont ils sont poussés sur:
stach.résultats de push (): 1 2 3 4 5
pile.pop() résultats: 5 4 3 2 1 (donc: de droite à gauche)
Vous pourriez profiter de cette:
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;
}
Ceci est mon implémentation, une pile est assez bonne. Une inversion est faite avant la boucle de 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;
}