خوارزمية الرسم البياني للعثور على كافة الاتصالات بين القمم التعسفية

Question

أحاول تحديد أفضل خوارزمية فعالة من حيث الوقت لإنجاز المهمة الموضحة أدناه.

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

تحتوي كافة السجلات الموجودة في المجموعة على معلومات الاتصال (أي.لا توجد سجلات يتيمة؛يتصل كل سجل في المجموعة بسجل واحد أو أكثر في المجموعة).

أريد اختيار أي سجلين من المجموعة وأن أكون قادرًا على إظهار جميع المسارات البسيطة بين السجلات المختارة.أعني بـ "المسارات البسيطة" المسارات التي لا تحتوي على سجلات متكررة في المسار (أيمسارات محدودة فقط).

ملحوظة:سيكون السجلان المختاران مختلفين دائمًا (أي.لن تكون قمة البداية والنهاية هي نفسها أبدًا؛لا دورات).

على سبيل المثال:

    If I have the following records:
        A, B, C, D, E

    and the following represents the connections: 
        (A,B),(A,C),(B,A),(B,D),(B,E),(B,F),(C,A),(C,E),
        (C,F),(D,B),(E,C),(E,F),(F,B),(F,C),(F,E)

        [where (A,B) means record A connects to record B]

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

   All paths connecting B to E:
      B->E
      B->F->E
      B->F->C->E
      B->A->C->E
      B->A->C->F->E

هذا مثال، عمليًا قد يكون لدي مجموعات تحتوي على مئات الآلاف من السجلات.

Answer 1

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

لقد لاحظت أن الرسم البياني الذي حددته أعلاه له حافة واحدة فقط وهي الاتجاه (B,E).هل كان هذا خطأ مطبعي أم أنه رسم بياني موجه بالفعل؟هذا الحل يعمل بغض النظر.آسف لأنني لم أتمكن من القيام بذلك في لغة C، فأنا ضعيف بعض الشيء في هذا المجال.أتوقع أنك ستتمكن من ترجمة كود Java هذا دون الكثير من المتاعب.

الرسم البياني جافا:

import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;

public class Graph {
    private Map<String, LinkedHashSet<String>> map = new HashMap();

    public void addEdge(String node1, String node2) {
        LinkedHashSet<String> adjacent = map.get(node1);
        if(adjacent==null) {
            adjacent = new LinkedHashSet();
            map.put(node1, adjacent);
        }
        adjacent.add(node2);
    }

    public void addTwoWayVertex(String node1, String node2) {
        addEdge(node1, node2);
        addEdge(node2, node1);
    }

    public boolean isConnected(String node1, String node2) {
        Set adjacent = map.get(node1);
        if(adjacent==null) {
            return false;
        }
        return adjacent.contains(node2);
    }

    public LinkedList<String> adjacentNodes(String last) {
        LinkedHashSet<String> adjacent = map.get(last);
        if(adjacent==null) {
            return new LinkedList();
        }
        return new LinkedList<String>(adjacent);
    }
}

جافا البحث:

import java.util.LinkedList;

public class Search {

    private static final String START = "B";
    private static final String END = "E";

    public static void main(String[] args) {
        // this graph is directional
        Graph graph = new Graph();
        graph.addEdge("A", "B");
        graph.addEdge("A", "C");
        graph.addEdge("B", "A");
        graph.addEdge("B", "D");
        graph.addEdge("B", "E"); // this is the only one-way connection
        graph.addEdge("B", "F");
        graph.addEdge("C", "A");
        graph.addEdge("C", "E");
        graph.addEdge("C", "F");
        graph.addEdge("D", "B");
        graph.addEdge("E", "C");
        graph.addEdge("E", "F");
        graph.addEdge("F", "B");
        graph.addEdge("F", "C");
        graph.addEdge("F", "E");
        LinkedList<String> visited = new LinkedList();
        visited.add(START);
        new Search().depthFirst(graph, visited);
    }

    private void depthFirst(Graph graph, LinkedList<String> visited) {
        LinkedList<String> nodes = graph.adjacentNodes(visited.getLast());
        // examine adjacent nodes
        for (String node : nodes) {
            if (visited.contains(node)) {
                continue;
            }
            if (node.equals(END)) {
                visited.add(node);
                printPath(visited);
                visited.removeLast();
                break;
            }
        }
        for (String node : nodes) {
            if (visited.contains(node) || node.equals(END)) {
                continue;
            }
            visited.addLast(node);
            depthFirst(graph, visited);
            visited.removeLast();
        }
    }

    private void printPath(LinkedList<String> visited) {
        for (String node : visited) {
            System.out.print(node);
            System.out.print(" ");
        }
        System.out.println();
    }
}

مخرجات البرنامج:

B E 
B A C E 
B A C F E 
B F E 
B F C E 

Answer 2

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

تم العثور على تقنية ذكية باستخدام Petri Nets هنا

Answer 3

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

أي شخص يريد أن يختار هذا على حدة.

• [p] هي قائمة القمم التي تمثل المسار الحالي.

• [x] هي قائمة بالمسارات التي تستوفي المعايير

• [s] هي قمة المصدر

• [د] هي قمة الوجهة

• [c] هي القمة الحالية (وسيطة روتين PathFind)

افترض أن هناك طريقة فعالة للبحث عن القمم المجاورة (السطر 6).

     1 PathList [p]
     2 ListOfPathLists [x]
     3 Vertex [s], [d]

     4 PathFind ( Vertex [c] )
     5     Add [c] to tail end of list [p]
     6     For each Vertex [v] adjacent to [c]
     7         If [v] is equal to [d] then
     8             Save list [p] in [x]
     9         Else If [v] is not in list [p]
    10             PathFind([v])
    11     Next For
    12     Remove tail from [p]
    13 Return

Answer 4

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

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

# a generator function to find all simple paths between two nodes in a
# graph, represented as a dictionary that maps nodes to their neighbors
def find_simple_paths(graph, start, end):
    visited = set()
    visited.add(start)

    nodestack = list()
    indexstack = list()
    current = start
    i = 0

    while True:
        # get a list of the neighbors of the current node
        neighbors = graph[current]

        # find the next unvisited neighbor of this node, if any
        while i < len(neighbors) and neighbors[i] in visited: i += 1

        if i >= len(neighbors):
            # we've reached the last neighbor of this node, backtrack
            visited.remove(current)
            if len(nodestack) < 1: break  # can't backtrack, stop!
            current = nodestack.pop()
            i = indexstack.pop()
        elif neighbors[i] == end:
            # yay, we found the target node! let the caller process the path
            yield nodestack + [current, end]
            i += 1
        else:
            # push current node and index onto stacks, switch to neighbor
            nodestack.append(current)
            indexstack.append(i+1)
            visited.add(neighbors[i])
            current = neighbors[i]
            i = 0

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

يستخدم هذا الرمز أيضًا رمزًا منفصلاً visited set، الذي يحتوي دائمًا على العقدة الحالية وأي عقد في المكدس، للسماح لي بالتحقق بكفاءة مما إذا كانت العقدة جزءًا من المسار الحالي بالفعل.إذا كانت لغتك تحتوي على بنية بيانات "مجموعة مرتبة" توفر عمليات الدفع/البوب ​​الفعالة الشبيهة بالمكدس و استعلامات العضوية الفعالة، يمكنك استخدام ذلك لمكدس العقدة والتخلص من العناصر المنفصلة visited تعيين.

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

فيما يلي بعض رموز الاختبار التي توضح كيفية عمل الوظيفة المذكورة أعلاه:

# test graph:
#     ,---B---.
#     A   |   D
#     `---C---'
graph = {
    "A": ("B", "C"),
    "B": ("A", "C", "D"),
    "C": ("A", "B", "D"),
    "D": ("B", "C"),
}

# find paths from A to D
for path in find_simple_paths(graph, "A", "D"): print " -> ".join(path)

يؤدي تشغيل هذا الرمز على الرسم البياني الموضح إلى إنتاج المخرجات التالية:

A -> B -> C -> D
A -> B -> D
A -> C -> B -> D
A -> C -> D

لاحظ أنه على الرغم من أن هذا الرسم البياني غير موجه (أيجميع حوافها تسير في الاتجاهين)، تعمل الخوارزمية أيضًا مع الرسوم البيانية الموجهة التعسفية.على سبيل المثال، إزالة C -> B الحافة (عن طريق إزالة B من قائمة الجيران C) ينتج نفس الإخراج باستثناء المسار الثالث (A -> C -> B -> D)، وهو ما لم يعد ممكنا.

---

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

على سبيل المثال، ضع في اعتبارك مهمة العثور على جميع المسارات من A إلى B على رسم بياني غير موجه حيث تحتوي عقدة البداية A على جارتين:العقدة المستهدفة B (التي لا تحتوي على جيران آخرين غير A) والعقدة C التي تعد جزءًا من a زمرة ل نعقد 1+، مثل هذا:

graph = {
    "A": ("B", "C"),
    "B": ("A"),
    "C": ("A", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
    "D": ("C", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
    "E": ("C", "D", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
    "F": ("C", "D", "E", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
    "G": ("C", "D", "E", "F", "H", "I", "J", "K", "L", "M", "N", "O"),
    "H": ("C", "D", "E", "F", "G", "I", "J", "K", "L", "M", "N", "O"),
    "I": ("C", "D", "E", "F", "G", "H", "J", "K", "L", "M", "N", "O"),
    "J": ("C", "D", "E", "F", "G", "H", "I", "K", "L", "M", "N", "O"),
    "K": ("C", "D", "E", "F", "G", "H", "I", "J", "L", "M", "N", "O"),
    "L": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "M", "N", "O"),
    "M": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "N", "O"),
    "N": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "O"),
    "O": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N"),
}

من السهل أن نرى أن المسار الوحيد بين A وB هو المسار المباشر، ولكن DFS الساذج الذي يبدأ من العقدة A سيضيع O(ن!) الوقت بلا جدوى في استكشاف المسارات داخل الزمرة، على الرغم من أنه من الواضح (للإنسان) أنه لا يمكن لأي من هذه المسارات أن يؤدي إلى B.

يمكن للمرء أيضًا البناء DAGs مع خصائص مماثلة، على سبيل المثال.من خلال ربط عقدة البداية A بالعقدة المستهدفة B والعقدتين الأخريين C₁ و ج₂, ، وكلاهما متصل بالعقد D₁ و د₂, ، وكلاهما متصل بـ E₁ و إي₂, ، وما إلى ذلك وهلم جرا.ل ن طبقات العقد مرتبة على هذا النحو، فإن البحث الساذج عن جميع المسارات من A إلى B سيؤدي في النهاية إلى إضاعة O(2^ن) الوقت لفحص جميع الطرق المسدودة المحتملة قبل الاستسلام.

بالطبع، إضافة حافة إلى العقدة المستهدفة B من إحدى العقد في الزمرة (بخلاف C)، أو من الطبقة الأخيرة من DAG، كان إنشاء عدد كبير جدًا من المسارات المحتملة من A إلى B، ولا تستطيع خوارزمية البحث المحلية البحتة أن تحدد مسبقًا ما إذا كانت ستجد مثل هذه الميزة أم لا.وهكذا، بمعنى ما، الفقراء حساسية الإخراج يرجع سبب عمليات البحث الساذجة هذه إلى افتقارهم إلى الوعي بالبنية العالمية للرسم البياني.

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

Answer 5

فيما يلي نسخة عودية ذات مظهر أفضل منطقيًا مقارنة بالطابق الثاني.

public class Search {

private static final String START = "B";
private static final String END = "E";

public static void main(String[] args) {
    // this graph is directional
    Graph graph = new Graph();
    graph.addEdge("A", "B");
    graph.addEdge("A", "C");
    graph.addEdge("B", "A");
    graph.addEdge("B", "D");
    graph.addEdge("B", "E"); // this is the only one-way connection
    graph.addEdge("B", "F");
    graph.addEdge("C", "A");
    graph.addEdge("C", "E");
    graph.addEdge("C", "F");
    graph.addEdge("D", "B");
    graph.addEdge("E", "C");
    graph.addEdge("E", "F");
    graph.addEdge("F", "B");
    graph.addEdge("F", "C");
    graph.addEdge("F", "E");
    List<ArrayList<String>> paths = new ArrayList<ArrayList<String>>();
    String currentNode = START;
    List<String> visited = new ArrayList<String>();
    visited.add(START);
    new Search().findAllPaths(graph, seen, paths, currentNode);
    for(ArrayList<String> path : paths){
        for (String node : path) {
            System.out.print(node);
            System.out.print(" ");
        }
        System.out.println();
    }   
}

private void findAllPaths(Graph graph, List<String> visited, List<ArrayList<String>> paths, String currentNode) {        
    if (currentNode.equals(END)) { 
        paths.add(new ArrayList(Arrays.asList(visited.toArray())));
        return;
    }
    else {
        LinkedList<String> nodes = graph.adjacentNodes(currentNode);    
        for (String node : nodes) {
            if (visited.contains(node)) {
                continue;
            } 
            List<String> temp = new ArrayList<String>();
            temp.addAll(visited);
            temp.add(node);          
            findAllPaths(graph, temp, paths, node);
        }
    }
}
}

مخرجات البرنامج

B A C E 

B A C F E 

B E

B F C E

B F E 

Answer 6

الحل في كود Cيعتمد على DFS الذي يستخدم الحد الأدنى من الذاكرة.

#include <stdio.h>
#include <stdbool.h>

#define maxN    20  

struct  nodeLink
{

    char node1;
    char node2;

};

struct  stack
{   
    int sp;
    char    node[maxN];
};   

void    initStk(stk)
struct  stack   *stk;
{
    int i;
    for (i = 0; i < maxN; i++)
        stk->node[i] = ' ';
    stk->sp = -1;   
}

void    pushIn(stk, node)
struct  stack   *stk;
char    node;
{

    stk->sp++;
    stk->node[stk->sp] = node;

}    

void    popOutAll(stk)
struct  stack   *stk;
{

    char    node;
    int i, stkN = stk->sp;

    for (i = 0; i <= stkN; i++)
    {
        node = stk->node[i];
        if (i == 0)
            printf("src node : %c", node);
        else if (i == stkN)
            printf(" => %c : dst node.\n", node);
        else
            printf(" => %c ", node);
    }

}


/* Test whether the node already exists in the stack    */
bool    InStack(stk, InterN)
struct  stack   *stk;
char    InterN;
{

    int i, stkN = stk->sp;  /* 0-based  */
    bool    rtn = false;    

    for (i = 0; i <= stkN; i++)
    {
        if (stk->node[i] == InterN)
        {
            rtn = true;
            break;
        }
    }

    return     rtn;

}

char    otherNode(targetNode, lnkNode)
char    targetNode;
struct  nodeLink    *lnkNode;
{

    return  (lnkNode->node1 == targetNode) ? lnkNode->node2 : lnkNode->node1;

}

int entries = 8;
struct  nodeLink    topo[maxN]    =       
    {
        {'b', 'a'}, 
        {'b', 'e'}, 
        {'b', 'd'}, 
        {'f', 'b'}, 
        {'a', 'c'},
        {'c', 'f'}, 
        {'c', 'e'},
        {'f', 'e'},               
    };

char    srcNode = 'b', dstN = 'e';      

int reachTime;  

void    InterNode(interN, stk)
char    interN;
struct  stack   *stk;
{

    char    otherInterN;
    int i, numInterN = 0;
    static  int entryTime   =   0;

    entryTime++;

    for (i = 0; i < entries; i++)
    {

        if (topo[i].node1 != interN  && topo[i].node2 != interN) 
        {
            continue;   
        }

        otherInterN = otherNode(interN, &topo[i]);

        numInterN++;

        if (otherInterN == stk->node[stk->sp - 1])
        {
            continue;   
        }

        /*  Loop avoidance: abandon the route   */
        if (InStack(stk, otherInterN) == true)
        {
            continue;   
        }

        pushIn(stk, otherInterN);

        if (otherInterN == dstN)
        {
            popOutAll(stk);
            reachTime++;
            stk->sp --;   /*    back trace one node  */
            continue;
        }
        else
            InterNode(otherInterN, stk);

    }

        stk->sp --;

}


int    main()

{

    struct  stack   stk;

    initStk(&stk);
    pushIn(&stk, srcNode);  

    reachTime = 0;
    InterNode(srcNode, &stk);

    printf("\nNumber of all possible and unique routes = %d\n", reachTime);

}

Answer 7

لقد قمت بحل مشكلة مشابهة لهذه مؤخرًا، بدلاً من كل الحلول كنت مهتمًا فقط بالأقصر.

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

تبدأ بسجل واحد في قائمة الانتظار، والذي يحتوي على عقدة البداية ومسار فارغ.

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

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

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

إذا كنت تريد المزيد من الكود الكاذب، فقم بنشر تعليق أو شيء من هذا القبيل، وسوف أشرح ذلك بالتفصيل.

Answer 8

أعتقد أنه يجب عليك وصف مشكلتك الحقيقية وراء هذا.أقول هذا لأنك تطلب شيئًا يوفر الوقت، ومع ذلك يبدو أن الإجابة على المشكلة تنمو بشكل كبير!

لذلك لا أتوقع خوارزمية أفضل من شيء أسي.

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

باستخدام العودية:

static bool[] visited;//all false
Stack<int> currentway; initialize empty

function findnodes(int nextnode)
{
if (nextnode==destnode)
{
  print currentway 
  return;
}
visited[nextnode]=true;
Push nextnode to the end of currentway.
for each node n accesible from nextnode:
  findnodes(n);
visited[nextnode]=false; 
pop from currenteay
}

أم أن هذا خطأ؟

يحرر:اه ونسيت:يجب عليك التخلص من المكالمات العودية باستخدام مكدس العقدة هذا

Answer 9

المبدأ الأساسي هو أنه لا داعي للقلق بشأن الرسوم البيانية. هذه مشكلة قياسية تُعرف باسم مشكلة الاتصال الديناميكي.هناك الأنواع التالية من الطرق التي يمكنك من خلالها تحقيق العقد المتصلة أم لا:

1. البحث السريع
2. الاتحاد السريع
3. خوارزمية محسنة (مزيج من الاثنين)

إليك رمز C الذي جربته مع الحد الأدنى من التعقيد الزمني O(log*n) وهذا يعني أنه بالنسبة لقائمة الحواف 65536، فإنها تتطلب 4 عمليات بحث وبالنسبة لـ 2^65536، فإنها تتطلب 5 عمليات بحث.أشارك تنفيذي من الخوارزمية: دورة الخوارزمية من جامعة برينستون

نصيحة:يمكنك العثور على حل Java من الرابط المشترك أعلاه مع التوضيحات المناسبة.

/* Checking Connection Between Two Edges */

#include<stdio.h>
#include<stdlib.h>
#define MAX 100

/*
  Data structure used

vertex[] - used to Store The vertices
size - No. of vertices
sz[] - size of child's
*/

/*Function Declaration */
void initalize(int *vertex, int *sz, int size);
int root(int *vertex, int i);
void add(int *vertex, int *sz, int p, int q);
int connected(int *vertex, int p, int q);

int main() //Main Function
{ 
char filename[50], ch, ch1[MAX];
int temp = 0, *vertex, first = 0, node1, node2, size = 0, *sz;
FILE *fp;


printf("Enter the filename - "); //Accept File Name
scanf("%s", filename);
fp = fopen(filename, "r");
if (fp == NULL)
{
    printf("File does not exist");
    exit(1);
}
while (1)
{
    if (first == 0) //getting no. of vertices
    {
        ch = getc(fp);
        if (temp == 0)
        {
            fseek(fp, -1, 1);
            fscanf(fp, "%s", &ch1);
            fseek(fp, 1, 1);
            temp = 1;
        }
        if (isdigit(ch))
        {
            size = atoi(ch1);
            vertex = (int*) malloc(size * sizeof(int));     //dynamically allocate size  
            sz = (int*) malloc(size * sizeof(int));
            initalize(vertex, sz, size);        //initialization of vertex[] and sz[]
        }
        if (ch == '\n')
        {
            first = 1;
            temp = 0;
        }
    }
    else
    {
        ch = fgetc(fp);
        if (isdigit(ch))
            temp = temp * 10 + (ch - 48);   //calculating value from ch
        else
        {
            /* Validating the file  */

            if (ch != ',' && ch != '\n' && ch != EOF)
            {
                printf("\n\nUnkwown Character Detected.. Exiting..!");

                exit(1);
            }
            if (ch == ',')
                node1 = temp;
            else
            {
                node2 = temp;
                printf("\n\n%d\t%d", node1, node2);
                if (node1 > node2)
                {
                    temp = node1;
                    node1 = node2;
                    node2 = temp;
                }

                /* Adding the input nodes */

                if (!connected(vertex, node1, node2))
                    add(vertex, sz, node1, node2);
            }
            temp = 0;
        }

        if (ch == EOF)
        {
            fclose(fp);
            break;
        }
    }
}

do
{
    printf("\n\n==== check if connected ===");
    printf("\nEnter First Vertex:");
    scanf("%d", &node1);
    printf("\nEnter Second Vertex:");
    scanf("%d", &node2);

    /* Validating The Input */

    if( node1 > size || node2 > size )
    {
        printf("\n\n Invalid Node Value..");
        break;
    }

    /* Checking the connectivity of nodes */

    if (connected(vertex, node1, node2))
        printf("Vertex %d and %d are Connected..!", node1, node2);
    else
        printf("Vertex %d and %d are Not Connected..!", node1, node2);


    printf("\n 0/1:  ");

    scanf("%d", &temp);

} while (temp != 0);

free((void*) vertex);
free((void*) sz);


return 0;
}

void initalize(int *vertex, int *sz, int size) //Initialization of graph
{
int i;
for (i = 0; i < size; i++)
{
    vertex[i] = i;
    sz[i] = 0;
}
}
int root(int *vertex, int i)    //obtaining the root
{
while (i != vertex[i])
{
    vertex[i] = vertex[vertex[i]];
    i = vertex[i];
}
return i;
}

/* Time Complexity for Add --> logn */
void add(int *vertex, int *sz, int p, int q) //Adding of node
{
int i, j;
i = root(vertex, p);
j = root(vertex, q);

/* Adding small subtree in large subtree  */

if (sz[i] < sz[j])
{
    vertex[i] = j;
    sz[j] += sz[i];
}
else
{
    vertex[j] = i;
    sz[i] += sz[j];
}

}

/* Time Complexity for Search -->lg* n */

int connected(int *vertex, int p, int q) //Checking of  connectivity of nodes
{
/* Checking if root is same  */

if (root(vertex, p) == root(vertex, q))
    return 1;

return 0;
}

Answer 10

قد يكون هذا متأخرًا، ولكن إليك نفس إصدار C# من خوارزمية DFS في Java من Casey لاجتياز جميع المسارات بين عقدتين باستخدام المكدس.سهولة القراءة أفضل مع التكرار كما هو الحال دائمًا.

    void DepthFirstIterative(T start, T endNode)
    {
        var visited = new LinkedList<T>();
        var stack = new Stack<T>();

        stack.Push(start);

        while (stack.Count != 0)
        {
            var current = stack.Pop();

            if (visited.Contains(current))
                continue;

            visited.AddLast(current);

            var neighbours = AdjacentNodes(current);

            foreach (var neighbour in neighbours)
            {
                if (visited.Contains(neighbour))
                    continue;

                if (neighbour.Equals(endNode))
                {
                    visited.AddLast(neighbour);
                    printPath(visited));
                    visited.RemoveLast();
                    break;
                }
            }

            bool isPushed = false;
            foreach (var neighbour in neighbours.Reverse())
            {
                if (neighbour.Equals(endNode) || visited.Contains(neighbour) || stack.Contains(neighbour))
                {
                    continue;
                }

                isPushed = true;
                stack.Push(neighbour);
            }

            if (!isPushed)
                visited.RemoveLast();
        }
    }

This is a sample graph to test:

    // Sample graph. Numbers are edge ids
    //       1     3       
    //    A --- B --- C ----
    //    |     |  2       |
    //    | 4   ----- D    |
    //    ------------------

Answer 11

find_paths[s، t، d، k]

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

أنا شخصيا أجد خوارزمية النموذج find_paths[s, t, d, k] مفيدة، حيث:

• s هي عقدة البداية
• t هي العقدة المستهدفة
• d هو أقصى عمق للبحث
• k هو عدد المسارات التي يمكن العثور عليها

استخدام شكل اللانهاية الخاص بلغة البرمجة الخاصة بك لـ d و k سوف أعطيك كل المسارات§.

§ من الواضح إذا كنت تستخدم الرسم البياني الموجه وتريد كل شيء غير موجه المسارات بين s و t سيكون عليك تشغيل هذا في كلا الاتجاهين:

find_paths[s, t, d, k] <join> find_paths[t, s, d, k]

---

وظيفة مساعد

أنا شخصيا أحب التكرار، على الرغم من أنه قد يكون صعبا في بعض الأحيان، على أي حال دعونا أولا نحدد وظيفة المساعد لدينا:

def find_paths_recursion(graph, current, goal, current_depth, max_depth, num_paths, current_path, paths_found)
  current_path.append(current)

  if current_depth > max_depth:
    return

  if current == goal:
    if len(paths_found) <= number_of_paths_to_find:
      paths_found.append(copy(current_path))

    current_path.pop()
    return

  else:
    for successor in graph[current]:
    self.find_paths_recursion(graph, successor, goal, current_depth + 1, max_depth, num_paths, current_path, paths_found)

  current_path.pop()

الوظيفة الأساسية

مع هذا بعيدًا عن الطريق، تصبح الوظيفة الأساسية تافهة:

def find_paths[s, t, d, k]:
  paths_found = [] # PASSING THIS BY REFERENCE  
  find_paths_recursion(s, t, 0, d, k, [], paths_found)

---

أولا لنلاحظ بعض الأمور:

• الكود الزائف أعلاه عبارة عن مزيج من اللغات - ولكنه يشبه إلى حد كبير لغة بايثون (نظرًا لأنني كنت أقوم بالترميز فيها للتو).لن ينجح النسخ واللصق الصارم.
• [] هي قائمة غير مهيأة، استبدلها بما يعادلها من لغة البرمجة التي تختارها
• paths_found تم تمريره مرجع.من الواضح أن وظيفة العودية لا تُرجع أي شيء.التعامل مع هذا بشكل مناسب.
• هنا graph يفترض شكلاً من أشكال hashed بناء.هناك عدد كبير من الطرق لتنفيذ الرسم البياني.في كلتا الحالتين، graph[vertex] يحصل لك على قائمة القمم المجاورة في توجه الرسم البياني - اضبط وفقًا لذلك.
• يفترض هذا أنك قمت بالمعالجة المسبقة لإزالة "الأبازيم" (الحلقات الذاتية) والدورات والحواف المتعددة

Answer 12

وهنا فكرة من أعلى رأسي:

1. ابحث عن اتصال واحد.(من المحتمل أن يكون بحث العمق أولاً خوارزمية جيدة لهذا الغرض، نظرًا لأن طول المسار لا يهم.)
2. تعطيل الجزء الأخير.
3. حاول العثور على اتصال آخر من العقدة الأخيرة قبل الاتصال المعطل مسبقًا.
4. انتقل إلى 2 حتى لا يكون هناك المزيد من الاتصالات.

Answer 13

بقدر ما أستطيع أن أقول الحلول التي قدمها ريان فوكس (58343, ، مسيحي (58444)، ونفسك (58461) جيدة بقدر ما تحصل عليه.لا أعتقد أن اجتياز العرض أولاً يساعد في هذه الحالة، حيث أنك لن تحصل على جميع المسارات.على سبيل المثال، مع الحواف (A,B), (A,C), (B,C), (B,D) و (C,D) سوف تحصل على المسارات ABD و ACD, ، لكن لا ABCD.

Answer 14

لقد وجدت طريقة لتعداد جميع المسارات بما في ذلك المسارات اللانهائية التي تحتوي على حلقات.

http://blog.vjeux.com/2009/project/project-shortest-path.html

العثور على المسارات والدورات الذرية

Definition

ما نريد فعله هو إيجاد جميع المسارات الممكنة الممتدة من النقطة أ إلى النقطة ب.نظرًا لوجود دورات معنية، لا يمكنك المرور عليها وتعدادها جميعًا.بدلاً من ذلك، سيتعين عليك العثور على مسار ذري لا يتكرر وأصغر الدورات الممكنة (لا تريد أن تكرر دورتك نفسها).

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

هذا التعريف مفيد، ويصلح أيضًا للدورات:الدورة الذرية للنقطة أ هي مسار ذري يبدأ من النقطة أ وينتهي بالنقطة أ.

تطبيق

Atomic Paths A -> B

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

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

Freeing the list

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

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

Atomic Cycle A

البحث عن الدورة الذرية لـ A هو نفس البحث عن المسار الذري من A إلى A.ومع ذلك، هناك العديد من التحسينات التي يمكننا القيام بها.أولاً، عندما نصل إلى نقطة الوجهة، نريد حفظ المسار فقط إذا كان مجموع تكلفة الحواف سالبًا:نريد فقط أن نمر عبر دورات الامتصاص.

كما رأيت سابقًا، يتم اجتياز الرسم البياني بأكمله عند البحث عن مسار ذري.بدلاً من ذلك، يمكننا قصر منطقة البحث على المكون المتصل بقوة والذي يحتوي على A.يتطلب العثور على هذه المكونات اجتيازًا بسيطًا للرسم البياني باستخدام خوارزمية تارجان.

الجمع بين المسارات والدورات الذرية

في هذه المرحلة، لدينا جميع المسارات الذرية التي تنتقل من A إلى B وجميع الدورات الذرية لكل عقدة، متروكة لنا لتنظيم كل شيء للحصول على أقصر مسار.من الآن فصاعدًا سندرس كيفية العثور على أفضل مجموعة من الدورات الذرية في المسار الذري.

Answer 15

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

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

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

أنا مدون حول هذا الموضوع مؤخرًا، تم نشر مثال لتطبيق C++ في هذه العملية.

Answer 16

إضافة إلى إجابة Casey Watson، إليك تطبيق Java آخر.تهيئة العقدة التي تمت زيارتها بعقدة البداية.

private void getPaths(Graph graph, LinkedList<String> visitedNodes) {
                LinkedList<String> adjacent = graph.getAdjacent(visitedNodes.getLast());
                for(String node : adjacent){
                    if(visitedNodes.contains(node)){
                        continue;
                    }
                    if(node.equals(END)){
                        visitedNodes.add(node);
                        printPath(visitedNodes);
                        visitedNodes.removeLast();
                    }
                    visitedNodes.add(node);
                    getPaths(graph, visitedNodes);
                    visitedNodes.removeLast();  
                }
            }