أفضل خوارزمية للكشف عن دورات في الرسم البياني موجهة

Question

ما هو الأكثر كفاءة خوارزمية للكشف عن جميع دورات في الرسم البياني موجهة?

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

Answer 1

خوارزمية مكونات مرتبطة بقوة Tarjan في تمت O(|E| + |V|) تعقيد الوقت.

لخوارزميات أخرى، انظر مكونات مرتبطة بقوة في ويكيبيديا.

Answer 2

ونظرا إلى أن هذا هو الجدول الزمني للعمل، وأظن أنه عند نقطة معينة أنت ذاهب إلى <م> نوع لهم في الترتيب المقترح للتنفيذ.

إذا كان هذا هو الحال، ثم <م> نوع الطوبوغرافية تنفيذ يجوز في أي حال كشف دورات. لا UNIX tsort بالتأكيد. وأعتقد أنه من المرجح أن ذلك فمن أكثر كفاءة للكشف عن دورات في نفس الوقت tsorting، وليس في خطوة منفصلة.

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

<اقتباس فقرة>   

http://en.wikipedia.org/wiki/Topological_sorting

لديه الزائفة رمز لخوارزمية واحدة، وصفا موجزا لآخر من Tarjan. ديهما O(|V| + |E|) تعقيد الوقت.

Answer 3

وتبدأ مع DFS: وجود دورة إذا وفقط إذا كان <م> اكتشف العودة حافة خلال DFS . ثبت هذا نتيجة لtheorum البيضاء المسار.

Answer 4

وأبسط طريقة للقيام بذلك هو القيام اجتياز أول عمق (DFT) من الرسم البياني .

إذا الرسم البياني له القمم n، وهذا هو الوقت O(n) تعقيد الخوارزمية. وبما انك من المحتمل أن تفعل DFT بدءا من كل قمة، يصبح مجموع تعقيد O(n^2).

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

Answer 5

في رأيي الأكثر مفهومة خوارزمية للكشف عن دورة في توجيه الرسم البياني هو الرسم-التلوين-خوارزمية.

أساسا ، مبيان خوارزمية يمشي على الرسم البياني في DFS نحو (عمق أول البحث ، مما يعني أنه يستكشف الطريق تماما قبل استكشاف مسار آخر).عندما يجد تعود الحافة ، أنه يمثل الرسم البياني كما تحتوي على حلقة.

في عمق التفسير البياني تلوين الخوارزمية ، يرجى قراءة هذا المقال: http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

كما أنني توفر تنفيذ الرسم والتلوين في جافا سكريبت https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js

Answer 6

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

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

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

في حين أن هذا قد يبدو أن لديها تعقيد O(N*M) يجب أن نتذكر أن المكدس لديه محدودة جدا العمق (حيث N هو صغير) و أن م يصبح أصغر مع كل تبعية يمكنك التحقق من خارج بأنها "إعدام" بالاضافة الى ذلك يمكنك التوقف عن البحث عندما وجدت ورقة (حتى يمكنك أبدا يجب أن تحقق كل عقدة -> M سوف تكون صغيرة جدا).

في MetaMake ، أنا خلق الرسم البياني في شكل قائمة من القوائم ثم حذف كل عقدة كما المنفذة عليها والتي بطبيعة الحال خفض حجم البحث.أنا في الحقيقة لم لتشغيل مستقلة تحقق ، حدث كل ذلك تلقائيا أثناء التنفيذ العادي.

إذا كنت في حاجة الى "اختبار فقط" الوضع مجرد إضافة "تشغيل الجاف" العلم الذي يعطل التنفيذ الفعلي وظائف.

Answer 7

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

Answer 8

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

Answer 9

ووفقا ليما 22.11 من <لأ href = "https://books.google.com/books؟id=i-bUBQAAQBAJ&lpg=PP1&dq=cormen٪20introduction٪20to٪20algorithms&pg=PP1#v=onepage&q=cormen٪20introduction ٪ 20to٪ 20algorithms وو = كاذبة "يختلط =" نوفولو noreferrer "> Cormen آخرون، <م> مقدمة إلى الخوارزميات (وCLRS):.

<اقتباس فقرة>   

وهناك مخطط موجه G هو احلقي إذا وفقط إذا كان البحث بالعمق أولا من G غلة لا يعود الحواف.

تم ذكر هذا في عدة إجابات. هنا أنا أيضا توفير المثال رمز بناء على الفصل 22 من CLRS. ويوضح المثال الرسم البياني أدناه.

وCLRS "الزائفة رمز لبحث معمق الأول ما يلي:

في المثال في CLRS الشكل 22.4، الرسم البياني يتكون من اثنين من أشجار DFS: واحدة تتكون من العقد ش ، <م> ت ، <م> س ، و<م> ص ، والآخر من العقد <م> ث و <م> ض . كل شجرة تحتوي على واحدة الى الوراء حافة: واحد من س إلى <م> ت وآخر من ض إلى <م> ض (أ الذاتي حلقة).

ووتحقيق الرئيسي هو أن الحافة الخلفية مصادفة عندما، في وظيفة DFS-VISIT، في حين بالتكرار عبر v جيران u، واجه عقدة مع لون GRAY.

وكود بايثون يلي أضاف للتكيف من شبة الكود CLRS "مع شرط if الذي يكتشف دورات:

import collections


class Graph(object):
    def __init__(self, edges):
        self.edges = edges
        self.adj = Graph._build_adjacency_list(edges)

    @staticmethod
    def _build_adjacency_list(edges):
        adj = collections.defaultdict(list)
        for edge in edges:
            adj[edge[0]].append(edge[1])
        return adj


def dfs(G):
    discovered = set()
    finished = set()

    for u in G.adj:
        if u not in discovered and u not in finished:
            discovered, finished = dfs_visit(G, u, discovered, finished)


def dfs_visit(G, u, discovered, finished):
    discovered.add(u)

    for v in G.adj[u]:
        # Detect cycles
        if v in discovered:
            print(f"Cycle detected: found a back edge from {u} to {v}.")

        # Recurse into DFS tree
        if v not in discovered and v not in finished:
            dfs_visit(G, v, discovered, finished)

    discovered.remove(u)
    finished.add(u)

    return discovered, finished


if __name__ == "__main__":
    G = Graph([
        ('u', 'v'),
        ('u', 'x'),
        ('v', 'y'),
        ('w', 'y'),
        ('w', 'z'),
        ('x', 'v'),
        ('y', 'x'),
        ('z', 'z')])

    dfs(G)

لاحظ أنه في هذا المثال، لا يتم القبض على time في شبة الكود CLRS لأننا مهتمون فقط في الكشف عن دورات. وهناك أيضا بعض التعليمات البرمجية النمطي لبناء تمثيل قائمة الجوار رسم بياني من قائمة الحواف.

عند تنفيذ هذا السيناريو، فإنه يطبع الإخراج التالي:

Cycle detected: found a back edge from x to v.
Cycle detected: found a back edge from z to z.

وهذه هي بالضبط الحواف الخلفية في المثال في CLRS الشكل 22.4.

Answer 10

والطريقة أفعل ذلك هي القيام ترتيب طوبولوجي، عد عدد من القمم التي تمت زيارتها. إذا كان هذا العدد أقل من العدد الإجمالي للرؤوس في DAG، لديك دورة.

Answer 11

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

Answer 12

https://mathoverflow.net/questions/16393/finding-a-cycle من ناتجها ذات طول ثابت أنا أحب هذا الحل الأفضل خصيصا لمدة 4 طول:)

وأيضا يقول المعالج فيز عليك أن تفعل O (V ^ 2). أعتقد أننا بحاجة O فقط (V) / O (V + E). إذا كان متصلا الرسم البياني ثم سوف DFS زيارة كافة العقد. إذا كان الرسم البياني والرسوم البيانية توصيل الفرعية ثم كل مرة ونحن تشغيل DFS على قمة من هذا الرسم البياني الفرعي سنجد القمم المتصلة وتميل الى النظر في هذه على المدى القادم لDFS. وبالتالي فإن إمكانية تشغيل لكل قمة الرأس غير صحيحة.

Answer 13

وكما قلت، لديك مجموعة من فرص العمل، فإنه يجب أن يتم تنفيذها في ترتيب معين. Topological sort منحك المطلوبة أجل جدولة الوظائف (أو لمشاكل التبعية إذا كانت direct acyclic graph). تشغيل dfs والحفاظ على القائمة، والبدء في إضافة عقدة في بداية القائمة، وإذا واجهتك عقدة الذي زار. ثم هل وجدت دورة في الرسم البياني معين.

Answer 14

إذا رسم بياني تلبية هذا العقار

|e| > |v| - 1

وثم يحتوي على الرسم البياني على الأقل على دورة.