Вопросы Теги

Обход графика C#

Вот пример, как читать 

&XMLReader.Open('Meeting.xml')     
&XMLReader.ReadType(1, 'MEMBERS')
&XMLReader.Read()
    Do While &XMLReader.Name <> 'MEMBERS'
        &MEMBER = &XMLReader.Value
        &XMLReader.Read()
    Enddo
&XMLReader.Close()

Вот документация: https://wiki.genexus.com/commwiki/servlet/wiki?6928,XMLReader+Data+Type [ 111],

10
задан Coral Doe 3 October 2012 в 06:06
поделиться

5 ответов

Отслеживайте узлы-предшественников. В самой легкой реализации это - словарь, и обычно обозначаемый как π в псевдокодах:

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];
}
10
ответ дан 4 December 2019 в 01:03
поделиться

Так как Вы не отслеживаете путь к "текущему" узлу в любом случае, необходимо будет создать это при нахождении цели. Если Ваш класс Узла имеет свойство Parent, Вы могли бы легко отследить в обратном порядке дерево для построения полного пути.

0
ответ дан 4 December 2019 в 01:03
поделиться

"Это", то есть, текущий экземпляр, "корень" графика, если существует такая вещь?

График является циклическим или нециклическим? Я боюсь, что не знаю все условия для теории графов.

Вот то, о чем я действительно задаюсь вопросом:

A -> B -> C ------> F
     B -> D -> E -> F

Вот мои вопросы:

  • Это произойдет?
  • Может "это" в Вашем коде когда-нибудь запускаться в B?
  • Что будет путь к F быть?

Если график никогда не присоединяется назад вместе, когда он распался, не содержит циклы, и "это" всегда будет базированием/начинанием графика, простой словарь обработает путь.

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
0
ответ дан 4 December 2019 в 01:03
поделиться

Peter почти корректен. Я не думаю, что можно сохранить ссылку на родительскую вершину в классе узла, потому что это изменяется в зависимости от вершины, в которой Вы запускаете свой поиск в ширину. Необходимо создать Родительский Словарь с ключами, являющимися узлами и значениями, являющимися родительскими узлами. Поскольку Вы посещаете каждую вершину (но прежде, чем обработать), Вы добавляете родителей к словарю. Затем можно идти по родительскому пути назад к корневой вершине.

0
ответ дан 4 December 2019 в 01:03
поделиться

Я пробовал использовать этот фрагмент, чтобы получить альтернативные пути от к вершине (вершины в моем коде), используя источник и судьбу, но просто не работает ... 

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':

См. предварительное изображение Вот: enter image description here

1
ответ дан 4 December 2019 в 01:03
поделиться
Другие вопросы по тегам:

Похожие вопросы: