كيف يمكنني التحقق مما إذا كان الرسم البياني الموجه هو Acyclic؟

Question

كيف يمكنني التحقق مما إذا كان الرسم البياني الموجه هو Acyclic؟ وكيف تسمى الخوارزمية؟ سأكون ممتنا مرجعا.

Answer 1

سأحاول فرز الرسم البياني طبولوجيا, ، وإذا كنت لا تستطيع، فسيكون لها دورات.

Answer 2

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

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

كما تشير روتجر، إذا كانت الرسم البياني الخاص بك غير متصل، فأنت بحاجة إلى تكرار البحث على كل مكون متصل.

كمرجع، خوارزمية المكونات المتصلة بشدة يرتبط ارتباطا وثيقا. كما سيساعدك في العثور على الدورات، وليس مجرد تقرير ما إذا كانت موجودة.

Answer 3

Lemma 22.11 على الكتاب Introduction to Algorithms (الطبعة الثانية) تنص على ما يلي:

الرسم البياني الموجه G هو Acyclic إذا وفقط إذا كان البحث أولا - البحث أولا عن G لا يعيد الحواف

Answer 4

الحل 1.： خوارزمية Kahn للتحقق من دورة. وبعد الفكرة الرئيسية: الحفاظ على قائمة انتظار حيث سيتم إضافة عقدة مع صفر في قائمة الانتظار. ثم تقشر عقدة واحدة تلو الأخرى حتى تكون الانتظار فارغة. تحقق مما إذا كانت أي حواف عقدة موجودة.

الحل 2: خوارزمية طرجان للتحقق من مكون متصل قوي.

Solution3.: DFS.. وبعد استخدم مجموعة عدد صحيح لعلامة الحالة الحالية للعقدة: IE 0 - الأم القراءة لم تتم زيارة هذه العقدة من قبل. -1 - يعني أن هذه العقدة قد تمت زيارة، ويجري زيارة عقد أطفالها. 1 - يعني أن هذه العقدة قد تمت زيارتها، ويتم ذلك. لذلك إذا كانت حالة العقدة -1 أثناء القيام DFS، فهذا يعني أنه يجب أن تكون هناك دورة موجودة.

Answer 5

الحل الذي قدمه SHUGGYCUK غير مكتمل لأنه قد لا يتحقق من جميع العقد.

def isDAG(nodes V):
    while there is an unvisited node v in V:
        bool cycleFound = dfs(v)
        if cyclefound:
            return false
    return true

هذا يحتوي على Timecomplexity O (N + M) أو O (n ^ 2)

Answer 6

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

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

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

• للحصول على الرسم البياني مع عقدة جذر واحدة تقوم بإرسال هذه العقدة وحشت فارغة
• للحصول على رسم بياني يحتوي على العقد الجذرية المتعددة التي تفتتحها في هذه العقد وتمرير Hashset فارغة جديد لكل تكرار

• عند التحقق من الدورات أسفل أي عقدة معينة، قم فقط بمرور هذه العقدة جنبا إلى جنب مع Hashset فارغة

  private bool FindCycle(int node, HashSet<int> path)
  {
  
      if (path.Contains(node))
          return true;
  
      var extendedPath = new HashSet<int>(path) {node};
  
      foreach (var child in GetChildren(node))
      {
          if (FindCycle(child, extendedPath))
              return true;
      }
  
      return false;
  }
  

Answer 7

لا ينبغي أن يكون هناك أي حافة خلفية أثناء القيام DF.Keep تتبع العقد التي تمت زيارتها بالفعل أثناء القيام DFS، إذا واجهت حافة بين العقدة الحالية والعقدة الحالية، ثم الرسم البياني له دورة.

Answer 8

فيما يلي رمز سريع للعثور عليه إذا كان الرسم البياني له دورات:

func isCyclic(G : Dictionary<Int,Array<Int>>,root : Int , var visited : Array<Bool>,var breadCrumb : Array<Bool>)-> Bool
{

    if(breadCrumb[root] == true)
    {
        return true;
    }

    if(visited[root] == true)
    {
        return false;
    }

    visited[root] = true;

    breadCrumb[root] = true;

    if(G[root] != nil)
    {
        for child : Int in G[root]!
        {
            if(isCyclic(G,root : child,visited : visited,breadCrumb : breadCrumb))
            {
                return true;
            }
        }
    }

    breadCrumb[root] = false;
    return false;
}


let G = [0:[1,2,3],1:[4,5,6],2:[3,7,6],3:[5,7,8],5:[2]];

var visited = [false,false,false,false,false,false,false,false,false];
var breadCrumb = [false,false,false,false,false,false,false,false,false];




var isthereCycles = isCyclic(G,root : 0, visited : visited, breadCrumb : breadCrumb)

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

Answer 9

هنا هو تطبيق روبي ل تقشر خوارزمية العقدة ورقة.

def detect_cycles(initial_graph, number_of_iterations=-1)
    # If we keep peeling off leaf nodes, one of two things will happen
    # A) We will eventually peel off all nodes: The graph is acyclic.
    # B) We will get to a point where there is no leaf, yet the graph is not empty: The graph is cyclic.
    graph = initial_graph
    iteration = 0
    loop do
        iteration += 1
        if number_of_iterations > 0 && iteration > number_of_iterations
            raise "prevented infinite loop"
        end

        if graph.nodes.empty?
            #puts "the graph is without cycles"
            return false
        end

        leaf_nodes = graph.nodes.select { |node| node.leaving_edges.empty? }

        if leaf_nodes.empty?
            #puts "the graph contain cycles"
            return true
        end

        nodes2 = graph.nodes.reject { |node| leaf_nodes.member?(node) }
        edges2 = graph.edges.reject { |edge| leaf_nodes.member?(edge.destination) }
        graph = Graph.new(nodes2, edges2)
    end
    raise "should not happen"
end

Answer 10

فقط كان لديه هذا السؤال في مقابلة جوجل.

الترتيب الطوبولوجي

يمكنك محاولة فرز شعوبيا، وهو O (V + E) حيث V هو عدد القمم، و E هو عدد الحواف. الرسم البياني الموجه هو Acyclic إذا وفقط إذا كان يمكن القيام بذلك.

إزالة ورقة العودية

قم بإزالة عقد الأوراق بشكل متكرر حتى لا يترك أي شيء، وإذا كان هناك أكثر من عقدة واحدة تركت لديك دورة. إلا إذا كنت مخطئا، فهذا هو O (v ^ 2 + ve).

DFS-Style ~ O (N + M)

ومع ذلك، فإن خوارزمية DFS-Esque الكفاءة، أسوأ الحالات O (V + E)، هي:

function isAcyclic (root) {
    const previous = new Set();

    function DFS (node) {
        previous.add(node);

        let isAcyclic = true;
        for (let child of children) {
            if (previous.has(node) || DFS(child)) {
                isAcyclic = false;
                break;
            }
        }

        previous.delete(node);

        return isAcyclic;
    }

    return DFS(root);
}