Algorithme graphique pour trouver toutes les connexions entre deux sommets arbitraires
https://stackoverflow.com/questions/58306
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'essaie de déterminer le meilleur algorithme efficace en termes de temps pour accomplir la tâche décrite ci-dessous.
J'ai un ensemble de dossiers.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-à-direaucun 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 dans 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-à-direchemins finis uniquement).
Note:Les deux enregistrements choisis seront toujours différents (c'est-à-direles sommets de début et de fin ne seront jamais les mêmes ;pas de cycles).
Par exemple:
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]
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.
All paths connecting B to 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.
La solution
Il semble que cela puisse être accompli avec une recherche en profondeur du graphique. La recherche en profondeur trouvera tous les chemins non cycliques entre deux nœuds. Cet algorithme doit être très rapide et s'adapter à de grands graphiques (la structure des données du graphique est clairsemée, elle 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).Était-ce une faute de frappe ou s'agit-il vraiment d'un graphique orienté ?Cette solution fonctionne malgré tout.Désolé, je n'ai pas pu le faire en C, je suis un peu faible dans ce domaine.J'espère que vous pourrez 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);
}
}
Recherche.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
Autres conseils
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 suit : »tous les chemins simples" et recommande un recherche en profondeur.CLRS fournit les algorithmes pertinents.
Une technique intelligente utilisant les réseaux de Petri est trouvée ici
Voici le pseudocode que j'ai trouvé.Il ne s’agit pas d’un dialecte de pseudocode particulier, mais il devrait être assez simple à suivre.
N’importe qui veut démonter cela.
[p] est une liste de sommets représentant le chemin actuel.
[x] est une liste de chemins qui répondent aux critères
[s] est le sommet source
[d] est le sommet de destination
[c] est le sommet actuel (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 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
Depuis l'implémentation DFS non récursive existante donnée dans cette réponse semble être cassé, permettez-moi de vous en fournir un 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 côté pratique yield mot-clé pour la mise en œuvre générateurs), mais il devrait être assez facile de le porter dans d'autres langues.
# 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 :un contenant les nœuds précédents dans le chemin actuel et un contenant l'index voisin actuel 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 retirons de 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 à mettre en œuvre pour les utilisateurs d'autres langages.
Ce code utilise également un visited set, 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 requêtes d'adhésion efficaces, vous pouvez l'utiliser pour la pile de nœuds et vous débarrasser des visited ensemble.
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 entendu, cette méthode ne vous permettra pas d'effectuer deux recherches sur le même graphique en parallèle, si pour une raison quelconque vous souhaitez le faire.
Voici un code de test démontrant le fonctionnement de la fonction donnée 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 l'exemple de graphique donné produit le résultat suivant :
A -> B -> C -> D A -> B -> D A -> C -> B -> D A -> C -> D
Notez que, bien que cet exemple de graphique ne soit pas orienté (c'est-à-diretoutes ses arêtes vont dans les deux sens), l'algorithme fonctionne également pour les graphes orientés arbitrairement.Par exemple, supprimer le C -> B bord (en supprimant B de 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 consistant à 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'un 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 gaspillera O(n!) du temps à explorer inutilement les chemins au sein de la clique, même s'il est évident (pour un humain) qu'aucun de ces chemins ne peut mener à B.
On peut aussi construire DAG avec des propriétés similaires, par ex.en faisant en sorte que le nœud de départ A connecte le nœud cible B et à deux autres nœuds C1 et C2, qui se connectent tous deux aux nœuds D1 et D2, qui se connectent tous deux à E1 et E2, et ainsi de suite.Pour n couches de nœuds disposées ainsi, une recherche naïve de tous les chemins de A à B finira par gaspiller O(2n) du temps à examiner toutes les impasses possibles avant d'abandonner.
Bien entendu, ajouter un bord au nœud cible B depuis l'un des nœuds de la clique (autre que C), ou depuis la dernière couche du DAG, serait créer un nombre exponentiellement grand de chemins possibles de A à B, et un algorithme de recherche purement local ne peut pas vraiment dire à l'avance s'il trouvera un tel bord ou non.Ainsi, d’une certaine manière, les pauvres sensibilité de sortie de telles recherches naïves sont dues à leur manque de connaissance de la structure globale du graphe.
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 à nœud unique, etc.) qui pourraient être utilisées pour éviter certaines de ces "impasses à temps exponentiel", je ne connais aucune méthode générale. astuce de prétraitement qui pourrait les éliminer tous 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 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 le faites pas contenir de telles impasses pathologiques.
Voici une version récursive logiquement plus belle par rapport au 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 un minimum de mémoire.
#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);
}
J'ai récemment résolu un problème similaire à celui-ci, au lieu de toutes les solutions, seules les plus courtes m'intéressaient.
J'ai utilisé une recherche itérative « en largeur d'abord » qui utilisait une file d'attente de statuts, dont chacun 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 comporte le nœud de départ et un chemin vide.
Chaque itération dans le code retire l'élément de la tête de liste et vérifie s'il s'agit d'une solution (le nœud atteint 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 aurez une boucle infinie.
si vous voulez un peu plus de pseudocode, postez un commentaire ou quelque chose du genre, et je développerai.
Je pense que vous devriez décrire votre véritable problème derrière cela.Je dis cela parce que vous demandez quelque chose de efficace, mais la réponse 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 parcourirais 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.
Utiliser 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 faux ?
modifier:Ah et j'ai oublié :Vous devez é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 que les nœuds soient connectés ou non :
- Recherche rapide
- Union rapide
- Algorithme amélioré (combinaison des deux)
Voici le code C que j'ai essayé avec une complexité temporelle minimale O(log*n) Cela signifie que pour 65536 listes d'arêtes, il nécessite 4 recherches et pour 2 ^ 65536, il nécessite 5 recherches.Je partage mon implémentation de l'algorithme : Cours d'algorithme de l'université de Princeton
CONSEIL:Vous pouvez trouver une 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;
}
C'est 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 la récursion 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();
}
}
This is a sample graph to test:
// Sample graph. Numbers are edge ids
// 1 3
// A --- B --- C ----
// | | 2 |
// | 4 ----- D |
// ------------------
find_paths[s, t, d, k]
Cette question est ancienne et a déjà répondu.Cependant, aucun ne montre peut-être un algorithme plus flexible pour accomplir la même chose.Je vais donc jeter mon chapeau sur le ring.
Personnellement, je trouve 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 d'infini de votre langage de programmation pour d et k vous donnera tous les chemins§.
§ évidemment si vous utilisez un graphe orienté et que vous voulez que tout non dirigé chemins entre s et t vous 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, mais 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
Cela étant dit, la fonction principale 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, notons quelques choses :
- le pseudo-code ci-dessus est un mélange de langages - mais ressemble le plus à Python (puisque je venais de coder dedans).Un copier-coller strict ne fonctionnera pas.
[]est une liste non initialisée, remplacez-la par l'équivalent pour le langage de programmation de votre choixpaths_foundest passé par référence.Il est clair que la fonction de récursivité ne renvoie rien.Gérez cela de manière appropriée.- ici
graphsuppose une certaine forme dehashedstructure.Il existe de nombreuses façons d’implémenter un graphique.De toute façon,graph[vertex]vous obtient une liste des sommets adjacents dans un dirigé graphique - ajuster en conséquence. - cela suppose que vous avez pré-traité pour supprimer les "boucles" (auto-boucles), les cycles et les multi-arêtes
Voici une pensée qui me vient à l’esprit :
- Trouvez une connexion.(La recherche en profondeur est probablement un bon algorithme pour cela, puisque la longueur du chemin n'a pas d'importance.)
- Désactivez le dernier segment.
- Essayez de trouver une autre connexion à partir du dernier nœud avant la connexion précédemment désactivée.
- Allez à 2 jusqu'à ce qu'il n'y ait plus de connexions.
Pour autant que je sache, les solutions proposées par Ryan Fox (58343, Christian (58444), et toi (58461) sont à peu près aussi bons que possible.Je ne crois pas que le parcours en largeur d'abord soit utile dans ce cas, car vous n'obtiendrez pas tous les chemins.Par exemple, avec des bords (A,B), (A,C), (B,C), (B,D) et (C,D) tu auras des chemins ABD et ACD, mais non ABCD.
J'ai trouvé un moyen d'énumérer tous les chemins, y compris ceux infinis contenant des boucles.
http://blog.vjeux.com/2009/project/project-shortest-path.html
Trouver des chemins et des 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 tous les énumérer.Au lieu de cela, vous devrez trouver un chemin atomique qui ne fait pas de boucle 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 n’exploitait pas toutes les possibilités.Après réflexion, j'ai compris que les nœuds ne sont pas importants, mais les bords le sont !Un chemin atomique est donc 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.
Mise en œuvre
Atomic Paths A -> B
Afin d’obtenir tout le chemin partant 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 tous les bords que nous avons déjà franchis.Avant d'accéder à 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 chaînée.Il s'agit essentiellement d'un arbre enchaîné dans l'ordre inverse.Une solution serait de doubler cette liste et, une fois tous les chemins atomiques trouvés, de libérer l'arbre du point de départ.
Mais une solution astucieuse consiste à utiliser un comptage de références (inspiré du 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 compteur de références est égal à 1.S'il est plus élevé, il vous suffit d'en supprimer un et d'arrêter.
Atomic Cycle A
Rechercher le cycle atomique de A revient à rechercher le chemin atomique de A à A.Cependant, nous pouvons effectuer plusieurs optimisations.Premièrement, lorsque nous arrivons au point de destination, nous souhaitons sauvegarder le chemin uniquement 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, l'ensemble du 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 connexe contenant A.La recherche de ces composants nécessite une simple traversée du graphique avec l'algorithme de Tarjan.
Combiner les chemins et les cycles atomiques
À ce stade, il nous reste tous les chemins atomiques qui vont de A à B et tous les cycles atomiques de chaque nœud, il nous reste à 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 l'ont habilement décrit certaines des autres affiches, le problème en un mot est celui de l'utilisation d'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 par 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 en arrière et revient au nœud le plus récent qu’elle n’a pas encore fini d’explorer.
je 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émarrage.
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();
}
}
