Вопрос
Этот алгоритм отлично справляется с обходом узлов графа.
Dictionary<Node, bool> visited = new Dictionary<Node, bool>();
Queue<Node> worklist = new Queue<Node>();
visited.Add(this, false);
worklist.Enqueue(this);
while (worklist.Count != 0)
{
Node node = worklist.Dequeue();
foreach (Node neighbor in node.Neighbors)
{
if (!visited.ContainsKey(neighbor))
{
visited.Add(neighbor, false);
worklist.Enqueue(neighbor);
}
}
}
Я могу использовать это, чтобы найти целевой узел на графике.Рабочий список удаляет из очереди (или выталкивает) элементы по мере обработки рабочего списка.Как только я найду цель, как я могу вернуть полный путь к узлу?
Обновить Я пытаюсь понять, как изменить путь к корню.Метод вызывается на корневом узле, после этого у дочерних элементов может быть два родителя, поэтому это не так просто, как вызвать родительское свойство на каждом узле и выполнить резервное копирование.
Цель метода - найти путь, а не перебирать все узлы или проверять, существует ли узел на самом деле.
Решение
Следите за узлами-предшественниками.В самой простой реализации это словарь, и обычно в псевдокодах он обозначается как π:
Dictionary<Node, bool> visited = new Dictionary<Node, bool>();
Dictionary<Node, Node> π = new Dictionary<Node, Node>();
Queue<Node> worklist = new Queue<Node>();
visited.Add(this, false);
worklist.Enqueue(this);
while (worklist.Count != 0)
{
Node node = worklist.Dequeue();
foreach (Node neighbor in node.Neighbors)
{
if (!visited.ContainsKey(neighbor))
{
visited.Add(neighbor, false);
π.Add(neighbor, node);
worklist.Enqueue(neighbor);
}
}
}
Затем вы можете выполнить итерацию по этим предшественникам, чтобы отследить путь от любого узла, скажем e
:
while (π[e] != null) {
Console.WriteLine(e);
e = π[e];
}
Другие советы
Я попытался использовать этот фрагмент, чтобы получить альтернативные пути от к вершине (вершины в моем коде), используя source и destiny, но просто не работает...
public String EncontrarMenorCaminho(Vertice o, Vertice d)
{
Dictionary<Vertice, bool> visited = new Dictionary<Vertice, bool>();
Dictionary<Vertice, Vertice> previous = new Dictionary<Vertice, Vertice>();
Queue<Vertice> worklist = new Queue<Vertice>();
String operacao = "Registro de operações realizadas:\r\n\r\n";
visited.Add(o, false);
worklist.Enqueue(o);
while (worklist.Count != 0)
{
Vertice v = worklist.Dequeue();
foreach (Vertice neighbor in EncontrarVizinhos(v))
{
if (!visited.ContainsKey(neighbor))
{
visited.Add(neighbor, false);
previous.Add(neighbor, v);
worklist.Enqueue(neighbor);
}
}
}
if (previous.Count > 0)
{
for (int p = 0; p < previous.Count; p++)
{
Vertice v1 = previous.ElementAt(p).Key;
Vertice v2 = previous.ElementAt(p).Value;
EncontrarAresta(v1, v2).Selecionado = true;
EncontrarAresta(v2, v1).Selecionado = true;
operacao += v1.Info.ToString() + "x" + v2.Info.ToString() + "\r\n";
}
}
List<Vertice> grupos = new List<Vertice>();
foreach (Aresta a in ArestasSelecionadas())
{
if (!grupos.Contains(a.Origem)) grupos.Add(a.Origem);
}
foreach (Vertice v in grupos)
{
int menorpeso = this.infinito;
foreach(Vertice vz in EncontrarVizinhos(v))
{
Aresta tmp = EncontrarAresta(v,vz);
if (tmp.Selecionado == true && tmp.Peso < menorpeso)
{
menorpeso = tmp.Peso;
}
else
{
tmp.Selecionado = false;
}
}
}
DesenharMapa();
return operacao;
В основном операция заключается в получении всех отмеченных ребер (Selecionado = true) и повторной проверке, если необходимо продолжить выбор...
В этом примере я хочу получить кратчайший путь от вершины 'N' к вершине 'Q':
Смотрите изображение предварительного просмотра здесь:
Является ли "это", то есть текущий экземпляр, "корнем" графика, если такая вещь существует?
Является ли график циклическим или ациклическим?Боюсь, я не знаю всех терминов теории графов.
Вот что меня действительно интересует:
A -> B -> C ------> F
B -> D -> E -> F
Вот мои вопросы:
- Произойдет ли это?
- Может ли "это" в вашем коде когда-нибудь начинаться с B?
- Каким будет путь к F?
Если график никогда не соединяется обратно после разделения, не содержит циклов, и "this" всегда будет корнем / началом графика, простой словарь обработает путь.
Dictionary<Node, Node> PreNodes = new Dictionary<Node, Node>();
для каждого узла, который вы посещаете, добавьте соседний узел в качестве ключа и узел, с которым он был соседом, в качестве значения.Это позволит вам, как только вы найдете целевой узел, вернуться назад, чтобы получить обратный путь.
Другими словами, словарь для приведенного выше графика после полного обхода будет:
B: A
C: B
D: B
E: D
F: C (or E, or both?)
Чтобы найти путь к электронному узлу, просто вернитесь назад:
E -> D -> B -> A
Который указывает вам путь:
A -> B -> D -> E
Поскольку вы не отслеживаете путь к "текущему" узлу постоянно, вам придется создать его, когда вы найдете цель.Если у вашего класса Node есть родительское свойство, вы можете легко вернуться вверх по дереву, чтобы построить полный путь.
Питер почти прав.Я не думаю, что вы можете сохранить ссылку на родительскую вершину в классе node, потому что она меняется в зависимости от вершины, с которой вы начинаете поиск в ширину.Вам нужно создать родительский словарь, в котором ключи являются узлами, а значения - родительскими узлами.Когда вы посещаете каждую вершину (но перед обработкой), вы добавляете родительские элементы в словарь.Затем вы можете подняться по родительскому пути обратно к корневой вершине.