C# الرسم البياني اجتياز

Question

هذه الخوارزمية يقوم بعمل كبير من عبور العقد في الرسم البياني.

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

يمكنني استخدام هذا أن تجد هدفا عقدة في الرسم البياني.على worklist dequeues (أو الملوثات العضوية الثابتة) البنود كما worklist تتم معالجتها.مرة أجد الهدف كيف يمكنني إرجاع المسار الكامل إلى العقدة?

التحديث أنا في محاولة لمعرفة كيفية عكس المسار إلى الجذر.طريقة ويطلق على عقدة الجذر, بعد ذلك, قد يكون الأطفال اثنين من الآباء والأمهات ، لذلك ليست بسيطة كما يدعو الوالد الملكية على كل عقدة و تعبر احتياطية.

الهدف من الطريقة هو العثور على الطريق ، وليس تكرار كل العقد ، أو لمعرفة ما إذا كانت العقدة موجودة.

Answer 1

تتبع السلف العقد.في أسهل تنفيذ هذا القاموس ، وعادة ما يرمز π في شبه رموز:

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

Answer 2

حاولت استخدام هذا مقتطف للحصول على مسارات بديلة من قمة الرأس (القمم في قانون بلدي) ، وذلك باستخدام المصدر والمصير ، ولكن ببساطة لا تعمل...

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) والتحقق مرة أخرى إذا كان من الضروري الاستمرار في المختارة...

في هذه العينة ، أريد الحصول على أقصر طريق من vertext 'N' إلى قمة 'Q':

رؤية معاينة الصورة هنا:

Answer 3

هو "هذا" ، وهذا هو ، المثيل الحالي ، "جذور" من الرسم البياني ، إذا كان هناك مثل هذا الشيء ؟

هو الرسم البياني دوري أو حلقية?أخشى أنا لا أعرف كل شروط نظرية الرسم البياني.

هنا ما كنت أتساءل حقا عن:

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

هنا هي بلدي الأسئلة:

• سوف يحدث هذا ؟
• أن "هذا" في التعليمات البرمجية الخاصة بك من أي وقت مضى البدء في "ب" ؟
• ما الطريق إلى F ؟

إذا كان الرسم البياني لم ينضم معا مرة أخرى عندما نفترق, لا تحتوي على دورات ، و "هذا" سوف دائما يكون root/بدء الرسم البياني بسيطة قاموس التعامل مع الطريق.

Dictionary<Node, Node> PreNodes = new Dictionary<Node, Node>();

على كل عقدة عليك زيارة ، إضافة المجاورة العقدة الرئيسية ، العقدة كان الجار من حيث القيمة.هذا سوف يسمح لك بمجرد العثور على الهدف عقدة إلى التراجع مرة أخرى للحصول على عكس المسار.

وبعبارة أخرى ، فإن قاموس الرسم البياني أعلاه ، بعد اجتياز كامل ليكون:

B: A
C: B
D: B
E: D
F: C (or E, or both?)

إلى العثور على المسار إلى E-عقدة ببساطة التراجع:

E -> D -> B -> A

والذي يعطي لك الطريق:

A -> B -> D -> E

Answer 4

منذ كنت لا تتبع المسار إلى "التيار" العقدة في جميع الأوقات سيكون لديك لبناء أنه عندما كنت قد وجدت الهدف.إذا كان لديك عقدة من الدرجة يكون أحد الوالدين المنشأة يمكنك بسهولة التراجع عن الشجرة لبناء المسار الكامل.

Answer 5

بيتر هو الصحيح تقريبا.أنا لا أعتقد أنك يمكن تخزين رابط الوالدين قمة في عقدة الفصل لأنه يتغير اعتمادا على قمة الرأس عند بدء تشغيل الخاص بك اتساع أول البحث.تحتاج إلى إنشاء الأم القاموس مع مفاتيح يجري العقد و قيم الوالدين العقد.كما يمكنك زيارة كل قمة (ولكن قبل المعالجة) إضافة الآباء إلى القاموس.ثم يمكنك المشي حتى الوالد طريق العودة إلى جذور الرأس.