J'essaie de déterminer le meilleur algorithme efficace pour accomplir la tâche décrite ci-dessous.

J'ai un ensemble de disques. Pour cet ensemble d'enregistrements, j'ai des données de connexion qui indiquent comment les paires d'enregistrements de cet ensemble se connectent les unes aux autres. Cela représente essentiellement un graphe non orienté, les enregistrements étant les sommets et les données de connexion les arêtes.

Tous les enregistrements de l'ensemble ont des informations de connexion (c'est-à-dire qu'aucun enregistrement orphelin n'est présent; chaque enregistrement de l'ensemble se connecte à un ou plusieurs autres enregistrements de l'ensemble).

Je souhaite choisir deux enregistrements quelconques de l'ensemble et pouvoir afficher tous les chemins simples entre les enregistrements choisis. Par "chemins simples", j'entends les chemins qui n'ont pas d'enregistrements répétés dans le chemin (c'est-à-dire des chemins finis uniquement).

Remarque: Les deux enregistrements choisis seront toujours différents (c'est-à-dire que les sommets de début et de fin ne seront jamais les mêmes; pas de cycles).

Par exemple:

    Si j'ai les enregistrements suivants:
        A, B, C, D, E

    et ce qui suit représente les connexions: 
        (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)

        [où (A, B) signifie que l'enregistrement A se connecte à l'enregistrement B]

Si je choisissais B comme enregistrement de départ et E comme enregistrement de fin, je voudrais trouver tous les chemins simples à travers les connexions d'enregistrement qui relieraient l'enregistrement B à l'enregistrement E.

   Tous les chemins reliant B à E:
      B-> E
      B-> F-> E
      B-> F-> C-> E
      B-> A-> C-> E
      B-> A-> C-> F-> E

Ceci est un exemple, en pratique je peux avoir des ensembles contenant des centaines de milliers d'enregistrements.

Il semble que cela puisse être accompli avec une recherche en profondeur du graphique. La recherche en profondeur d'abord trouvera tous les chemins non cycliques entre deux nœuds. Cet algorithme doit être très rapide et évoluer vers de grands graphes (la structure des données du graphe est clairsemée et n'utilise donc que la quantité de mémoire nécessaire).

J'ai remarqué que le graphique que vous avez spécifié ci-dessus n'a qu'un seul bord directionnel (B, E). S'agit-il d'une faute de frappe ou s'agit-il vraiment d'un graphique dirigé? Cette solution fonctionne indépendamment. Désolé je n'ai pas pu le faire en C, je suis un peu faible dans ce domaine. J'espère que vous serez en mesure de traduire ce code Java sans trop de problèmes.

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

Search.java:

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

Sortie du programme:

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

Le dictionnaire en ligne des algorithmes et des structures de données du National Institute of Standards and Technology (NIST) répertorie ce problème comme « tous les chemins simples» et recommande une recherche en profondeur d'abord . CLRS fournit les algorithmes pertinents.

Une technique intelligente utilisant des filets de Petri se trouve ici

Voici le pseudocode que j'ai trouvé. Ce n'est pas un dialecte de pseudocode particulier, mais devrait être assez simple à suivre.

N'importe qui veut séparer cela.

• [p] est une liste de sommets représentant le chemin courant.

• [x] est une liste de chemins où répondent aux critères

• [s] est le sommet source

• [d] est le sommet de destination

• [c] est le sommet courant (argument de la routine PathFind)

Supposons qu'il existe un moyen efficace de rechercher les sommets adjacents (ligne 6).

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

     4 PathFind (Vertex [c])
     5 Ajouter [c] à la fin de la liste [p]
     6 Pour chaque sommet [v] adjacent à [c]
     7 Si [v] est égal à [d] alors
     8 Enregistrer la liste [p] dans [x]
     9 Sinon si [v] n'est pas dans la liste [p]
    10 PathFind ([v])
    11 Suivant pour
    12 Retirez la queue de [p]
    13 Retour

Étant donné que l'implémentation DFS non récursive existante donnée dans cette réponse semble être interrompue, permettez-moi de vous en fournir une qui fonctionne réellement.

J'ai écrit ceci en Python, parce que je le trouve assez lisible et épuré par les détails d'implémentation (et parce qu'il a le yieldmot-clé pratique pour implémenter des générateurs ), mais il devrait être assez facile de porter vers d'autres langages.

# 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

Ce code maintient deux piles parallèles: l'une contenant les nœuds précédents dans le chemin actuel, et l'autre contenant l'index actuel du voisin pour chaque nœud de la pile de nœuds (afin que nous puissions reprendre l'itération à travers les voisins d'un nœud lorsque nous le faisons sauter la pile). J'aurais tout aussi bien pu utiliser une seule pile de paires (nœud, index), mais j'ai pensé que la méthode à deux piles serait plus lisible et peut-être plus facile à implémenter pour les utilisateurs d'autres langues.

Ce code utilise également un visitedensemble séparé , qui contient toujours le nœud actuel et tous les nœuds de la pile, pour me permettre de vérifier efficacement si un nœud fait déjà partie du chemin actuel. Si votre langage possède une structure de données «ensemble ordonné» qui fournit à la fois des opérations push / pop efficaces de type pile et des requêtes d'appartenance efficaces, vous pouvez l'utiliser pour la pile de nœuds et vous débarrasser de l' visitedensemble séparé .

Alternativement, si vous utilisez une classe / structure mutable personnalisée pour vos nœuds, vous pouvez simplement stocker un indicateur booléen dans chaque nœud pour indiquer s'il a été visité dans le cadre du chemin de recherche actuel. Bien sûr, cette méthode ne vous permettra pas d'exécuter deux recherches sur le même graphique en parallèle, si vous souhaitez le faire pour une raison quelconque.

Voici un code de test démontrant le fonctionnement de la fonction ci-dessus:

# 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)

L'exécution de ce code sur le graphique d'exemple donné produit la sortie suivante:

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

Notez que, bien que cet exemple de graphe ne soit pas orienté (c'est-à-dire que toutes ses arêtes vont dans les deux sens), l'algorithme fonctionne également pour les graphes dirigés arbitraires. Par exemple, la suppression du C -> Bbord (en supprimant Bde la liste des voisins de C) donne le même résultat sauf pour le troisième chemin ( A -> C -> B -> D), ce qui n'est plus possible.

Ps. Il est facile de construire des graphiques pour lesquels des algorithmes de recherche simples comme celui-ci (et les autres donnés dans ce fil) fonctionnent très mal.

Par exemple, considérons la tâche de trouver tous les chemins de A à B sur un graphe non orienté où le nœud de départ A a deux voisins: le nœud cible B (qui n'a pas d'autres voisins que A) et un nœud C qui fait partie d'une clique de n +1 nœuds, comme ceci:

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"),
}

Il est facile de voir que le seul chemin entre A et B est le chemin direct, mais un DFS naïf démarré à partir du nœud A perdra O ( n !) Temps à explorer inutilement les chemins au sein de la clique, même s'il est évident (pour un humain) que aucun de ces chemins ne peut conduire à B.

On peut également construire des DAG avec des propriétés similaires, par exemple en demandant au nœud de départ A de connecter le nœud cible B et à deux autres nœuds C ₁ et C ₂ , tous deux se connectant aux nœuds D ₁ et D ₂ , qui se connectent tous deux à E ₁ et E ₂ , et ainsi de suite. Pour n couches de nœuds disposés comme ceci, une recherche naïve de tous les chemins de A à B finira par gaspiller O (2 ⁿ ) temps à examiner toutes les impasses possibles avant d'abandonner.

Bien entendu, l' ajout d' un bord vers le noeud cible B à partir de l' un des noeuds dans la clique (autre que C), ou à partir de la dernière couche du DAG, serait de créer un nombre exponentiellement grand nombre de chemins possibles de A à B, et L'algorithme de recherche purement local ne peut pas vraiment dire à l'avance s'il trouvera un tel avantage ou non. Ainsi, dans un sens, la faible sensibilité de sortie de ces recherches naïves est due à leur manque de conscience de la structure globale du graphique.

Bien qu'il existe diverses méthodes de prétraitement (telles que l'élimination itérative des nœuds feuilles, la recherche de séparateurs de sommets à un seul nœud, etc.) qui pourraient être utilisées pour éviter certaines de ces "impasses à temps exponentiel", je ne connais aucun général astuce de prétraitement qui pourrait les éliminer dans tous les cas. Une solution générale serait de vérifier à chaque étape de la recherche si le nœud cible est toujours accessible (en utilisant une sous-recherche), et de revenir en arrière tôt si ce n'est pas le cas - mais hélas, cela ralentirait considérablement la recherche (au pire , proportionnellement à la taille du graphique) pour de nombreux graphiques qui ne contiennent pas de telles impasses pathologiques.

Voici une version récursive logiquement plus esthétique que celle du deuxième étage.

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

Sortie du programme

B A C E 

B A C F E 

B E

B F C E

B F E 

Solution en code C. Il est basé sur DFS qui utilise une mémoire minimale.

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

}

Cela peut être tard, mais voici la même version C # de l'algorithme DFS en Java de Casey pour parcourir tous les chemins entre deux nœuds à l'aide d'une pile. La lisibilité est meilleure avec récursif comme toujours.

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

Voici un exemple de graphique à tester:

    // Exemple de graphique. Les nombres sont des identifiants d'arête
    // 1 3       
    // A --- B --- C ----
    // | | 2 |
    // | 4 ----- D |
    // ------------------

J'ai récemment résolu un problème similaire à celui-ci, au lieu de toutes les solutions, je ne m'intéressais qu'aux plus courtes.

J'ai utilisé une recherche itérative `` largeur d'abord '' qui utilisait une file d'attente de statut `` dont chacune contenait un enregistrement contenant un point actuel sur le graphique et le chemin emprunté pour y arriver.

vous commencez avec un seul enregistrement dans la file d'attente, qui a le nœud de départ et un chemin vide.

Chaque itération dans le code enlève l'élément de la tête de la liste, et vérifie s'il s'agit d'une solution (le nœud auquel vous êtes arrivé est celui que vous voulez, si c'est le cas, nous avons terminé), sinon, il construit un nouveau élément de file d'attente avec les nœuds se connectant au nœud actuel et les chemins modifiés basés sur le chemin du nœud précédent, avec le nouveau saut attaché à la fin.

Maintenant, vous pouvez utiliser quelque chose de similaire, mais lorsque vous trouvez une solution, au lieu de vous arrêter, ajoutez cette solution à votre «liste trouvée» et continuez.

Vous devez garder une trace d'une liste de nœuds visités, afin de ne jamais revenir en arrière sur vous-même, sinon vous avez une boucle infinie.

si vous voulez un peu plus de pseudocode, postez un commentaire ou quelque chose, et je vais élaborer.

Je pense que vous devriez décrire votre vrai problème derrière tout cela. Je dis cela parce que vous demandez quelque chose de efficace en termes de temps, mais la réponse apportée au problème semble croître de façon exponentielle!

Par conséquent, je ne m'attendrais pas à un meilleur algorithme que quelque chose d'exponentiel.

Je ferais un retour en arrière et parcourais tout le graphique. Afin d'éviter les cycles, enregistrez tous les nœuds visités en cours de route. Lorsque vous revenez en arrière, décochez le nœud.

Utilisation de la récursivité:

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
}

Ou est-ce mal?

edit: Oh, et j'ai oublié: vous devriez éliminer les appels récursifs en utilisant cette pile de nœuds

Le principe de base est que vous n'avez pas à vous soucier des graphiques. Il s'agit d'un problème standard connu sous le nom de problème de connectivité dynamique. Il existe les types de méthodes suivants à partir desquels vous pouvez obtenir des nœuds connectés ou non:

1. Recherche rapide
2. Union rapide
3. Algorithme amélioré (combinaison des deux)

Voici le code C que j'ai essayé avec une complexité de temps minimale O (log * n) Cela signifie que pour 65536 liste d'arêtes, il nécessite 4 recherches et pour 2 ^ 65536, 5 recherches. Je partage ma mise en œuvre de l'algorithme: Cours d'algorithme de l'université de Princeton

CONSEIL: Vous pouvez trouver la solution Java à partir du lien partagé ci-dessus avec des explications appropriées.

/* 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;
}

find_paths [s, t, d, k]

Cette question est ancienne et répond déjà. Cependant, aucun ne montre peut-être un algorithme plus flexible pour accomplir la même chose. Alors je vais jeter mon chapeau dans le ring.

Je trouve personnellement un algorithme de la forme find_paths[s, t, d, k]utile, où:

• s est le nœud de départ
• t est le nœud cible
• d est la profondeur maximale à rechercher
• k est le nombre de chemins à trouver

Utiliser la forme de l'infini de votre langage de programmation pour det kvous donnera tous les chemins§.

§ évidemment si vous utilisez un graphe orienté et que vous voulez tous les chemins non dirigés entre set tvous devrez exécuter ceci dans les deux sens:

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

Fonction d'assistance

Personnellement, j'aime la récursivité, même si cela peut parfois être difficile, de toute façon définissons d'abord notre fonction d'assistance:

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()

Fonction principale

Avec cela à l'écart, la fonction de base est triviale:

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

Tout d'abord, remarquons une chose:

• le pseudo-code ci-dessus est un mélange de langages - mais ressemblant le plus fortement à python (puisque je codais juste dedans). Un copier-coller strict ne fonctionnera pas.
• [] est une liste non initialisée, remplacez-la par l'équivalent du langage de programmation de votre choix
• paths_foundest passé par référence . Il est clair que la fonction de récursivité ne renvoie rien. Manipulez cela de manière appropriée.
• ici graphsuppose une forme de hashedstructure. Il existe une multitude de façons d'implémenter un graphique. De toute façon, graph[vertex]vous obtient une liste des sommets adjacents dans une scène graphique - ajuster en conséquence.
• cela suppose que vous avez prétraité pour supprimer les «boucles» (auto-boucles), les cycles et les arêtes multiples

Voici une pensée qui vient du haut de ma tête:

1. Trouvez une connexion. (La recherche en profondeur d'abord est probablement un bon algorithme pour cela, car la longueur du chemin n'a pas d'importance.)
2. Désactivez le dernier segment.
3. Essayez de trouver une autre connexion à partir du dernier nœud avant la connexion précédemment désactivée.
4. Aller à 2 jusqu'à ce qu'il n'y ait plus de connexions.

Pour autant que je sache , les solutions données par Ryan Fox ( 58343 , Christian ( 58444 ) et vous-même ( 58461 ) sont à peu près aussi bonnes que possible. Je ne crois pas que la traversée en largeur d'abord aide dans ce cas, pas obtenir tous les chemins. par exemple, avec des bords (A,B), (A,C), (B,C), (B,D)et (C,D)vous obtiendrez des chemins ABDet ACD, mais pas ABCD.

J'ai trouvé un moyen d'énumérer tous les chemins, y compris les infinis contenant des boucles.

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

Recherche de chemins et de cycles atomiques

Definition

Ce que nous voulons faire, c'est trouver tous les chemins possibles allant du point A au point B. Puisqu'il y a des cycles impliqués, vous ne pouvez pas simplement les parcourir et les énumérer tous. Au lieu de cela, vous devrez trouver le chemin atomique qui ne boucle pas et les cycles les plus petits possibles (vous ne voulez pas que votre cycle se répète).

La première définition que j'ai prise d'un chemin atomique est un chemin qui ne passe pas deux fois par le même nœud. Cependant, j'ai découvert que cela ne prenait pas toutes les possibilités. Après quelques réflexions, j'ai compris que les nœuds ne sont pas importants, mais les bords le sont! Ainsi, un chemin atomique est un chemin qui ne passe pas deux fois par le même bord.

Cette définition est pratique, elle fonctionne aussi pour les cycles: un cycle atomique du point A est un chemin atomique qui va du point A et se termine au point A.

la mise en oeuvre

Atomic Paths A -> B

Afin d'obtenir tout le chemin à partir du point A, nous allons parcourir le graphe de manière récursive à partir du point A. En passant par un enfant, nous allons faire un lien enfant -> parent afin de connaître toutes les arêtes que nous ont déjà traversé. Avant d'aller à cet enfant, nous devons parcourir cette liste chaînée et nous assurer que le bord spécifié n'a pas déjà été parcouru.

Lorsque nous arrivons au point de destination, nous pouvons stocker le chemin que nous avons trouvé.

Freeing the list

Un problème survient lorsque vous souhaitez libérer la liste liée. Il s'agit essentiellement d'un arbre enchaîné dans l'ordre inverse. Une solution serait de double-lier cette liste et lorsque tous les chemins atomiques ont été trouvés, libérez l'arbre du point de départ.

Mais une solution intelligente consiste à utiliser un comptage de références (inspiré de Garbage Collection). Chaque fois que vous ajoutez un lien vers un parent, vous en ajoutez un à son nombre de références. Ensuite, lorsque vous arrivez à la fin d'un chemin, vous reculez et vous libérez tandis que le nombre de références est égal à 1. S'il est supérieur, vous en supprimez simplement un et vous arrêtez.

Atomic Cycle A

Rechercher le cycle atomique de A équivaut à rechercher le chemin atomique de A à A. Cependant, nous pouvons faire plusieurs optimisations. Premièrement, lorsque nous arrivons au point de destination, nous ne voulons sauvegarder le chemin que si la somme des coûts des arêtes est négative: nous voulons seulement passer par des cycles absorbants.

Comme vous l'avez vu précédemment, tout le graphe est parcouru lors de la recherche d'un chemin atomique. Au lieu de cela, nous pouvons limiter la zone de recherche au composant fortement connecté contenant A. La recherche de ces composants nécessite un simple parcours du graphe avec l'algorithme de Tarjan.

Combinaison de chemins et de cycles atomiques

À ce stade, nous avons tous les chemins atomiques qui vont de A à B et tous les cycles atomiques de chaque nœud, laissés à nous pour tout organiser pour obtenir le chemin le plus court. A partir de maintenant, nous allons étudier comment trouver la meilleure combinaison de cycles atomiques dans un chemin atomique.

Comme décrit habilement par certaines des autres affiches, le problème en un mot est celui d'utiliser un algorithme de recherche en profondeur d'abord pour rechercher de manière récursive dans le graphique toutes les combinaisons de chemins entre les nœuds d'extrémité communicants.

L'algorithme lui-même commence avec le nœud de départ que vous lui donnez, examine tous ses liens sortants et progresse en développant le premier nœud enfant de l'arbre de recherche qui apparaît, en cherchant progressivement de plus en plus profondément jusqu'à ce qu'un nœud cible soit trouvé, ou jusqu'à ce qu'il rencontre un nœud qui n'a pas d'enfants.

La recherche revient ensuite sur le nœud le plus récent qu'elle n'a pas encore fini d'explorer.

J'ai blogué sur ce sujet très récemment, en publiant un exemple d'implémentation C ++ dans le processus.

En plus de la réponse de Casey Watson, voici une autre implémentation Java. Initialisation du nœud visité avec le nœud de départ.

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