Graph-Algorithmus Zu Finden, Der Alle Verbindungen Zwischen Zwei Beliebigen Scheitelpunkten
https://stackoverflow.com/questions/58306
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich bin versucht zu bestimmen, die beste Zeit, effizienten Algorithmus, um die Aufgabe auszuführen, die unten beschrieben.
Ich habe eine Reihe von Datensätzen.Für diese Datensätze habe ich von Verbindungsdaten, die angibt, wie Paare von Datensätzen aus dieser Gruppe miteinander zu verbinden.Dies ist im Grunde stellt eine ungerichtete Graphen, mit dem die Datensätze der Scheitelpunkte und die Verbindungsdaten der Kanten.
Alle Datensätze in der festgelegt haben, Informationen über die Verbindung (d.h.keine verwaisten Datensätze vorhanden sind;jeder Datensatz in das set verbindet ein oder mehrere andere Datensätze in die set).
Ich möchten wählen Sie zwei beliebige Datensätze aus dem set und in der Lage sein zu zeigen, alle einfachen Pfade zwischen den ausgewählten Datensätze.Durch "einfache Wege" ich meine die Wege, die nicht wiederholt Datensätze in den Pfad (D. H.endliche Pfade nur).
Hinweis:Die beiden ausgewählten Datensätze werden immer anders sein (d.h.start-und end-vertex wird nie der gleiche sein;keine Zyklen).
Zum Beispiel:
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]
Wenn ich wählte, B wie mein Start-Datensatz und E, wie mein Ende aufnehmen, ich würde mir wünschen, finden Sie alle einfachen Pfade durch den record-verbindungen verbinden würde Rekord B Rekord 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
Dies ist ein Beispiel, in der Praxis, die ich haben kann-sets enthalten Hunderte oder Tausende von Datensätzen.
Lösung
Es scheint, dass dies erreicht werden kann, mit eine Tiefe-zuerst-Suche des Graphen. Die Tiefe-zuerst-Suche finden Sie alle nicht-zyklische Pfade zwischen zwei Knoten. Dieser Algorithmus sollte sehr schnell sein und Maßstab für große Graphen (graph-Datenstruktur ist spärlich, so dass es verwendet nur so viel Arbeitsspeicher, wie es erforderlich ist).
Ich bemerkte, dass die Grafik, die Sie oben angegeben hat nur eine Kante, die ist gerichtete (B,E).War das ein Tippfehler oder ist es wirklich ein gerichteter graph?Diese Lösung funktioniert unabhängig.Sorry, ich war nicht in der Lage, es zu tun in C, ich bin ein bisschen schwach in diesem Bereich.Ich erwarte, dass Sie in der Lage sein zu übersetzen in die Java-code ohne allzu viel Mühe, obwohl.
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();
}
}
Programm-Ausgabe:
B E
B A C E
B A C F E
B F E
B F C E
Andere Tipps
Das National Institute of Standards and Technology (NIST) online-Wörterbuch von Algorithmen und Daten-Strukturen, Listen dieses problem als "alle einfachen Pfade" und empfiehlt Tiefe-erste Suche.CLRS versorgt die einschlägigen algorithmen.
Eine clevere Technik mit Petri-Netzen ist gefunden hier
Hier ist der pseudocode ich kam mit.Dies ist keine Besondere pseudocode Dialekt, sollten aber einfach genug sein, um zu Folgen.
Wer will diesen pick apart.
[p] ist eine Liste von Scheitelpunkten, die den aktuellen Pfad.
[x] wird eine Liste der Pfade, in denen die Kriterien zu erfüllen
[s] ist die Quelle vertex
[d] ist das Ziel vertex
[c] ist der aktuelle Knoten (argument der PathFind routine)
Angenommen, es gibt eine effiziente Möglichkeit, um die benachbarten Knoten (Zeile 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
Da die bestehende nicht-rekursive DFS-Implementierung in diese Antwort scheint kaputt zu sein, lassen Sie mich eine, die tatsächlich funktioniert.
Ich habe geschrieben in Python, weil ich finde es ziemlich lesbar und übersichtlich durch Implementierungsdetails (und weil es die praktische yield Schlüsselwort für die Umsetzung Generatoren), aber es sollte ziemlich einfach sein, Anschluss an andere Sprachen.
# 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
Dieser code verwaltet zwei parallele Stapel:eine mit den früheren Knoten im aktuellen Pfad, und eine mit den aktuellen Nachbar-index für die einzelnen Knoten im node-stack (so, dass wir können fortsetzen, Durchlaufen die Nachbarn eines Knotens, wenn wir es pop wieder vom Stapel).Ich habe ebenso gut zu einem Stapel (node, index) Paaren, aber ich dachte, die zwei-Stapel-Methode wäre besser lesbar, und vielleicht einfacher zu implementieren, für Sprecher anderer Sprachen.
Dieser code wird auch verwendet eine separate visited set, das enthält immer den aktuellen Knoten und alle Knoten auf dem stack, um mich effizient zu überprüfen, ob ein Knoten bereits Teil des aktuellen Pfades.Wenn Ihre Sprache geschieht, um eine "geordnete Menge" Daten-Struktur, die bietet sowohl effiziente stack-wie push/pop-Operationen und effiziente Mitgliedschaft Anfragen, die Sie verwenden können, für die die Knoten stapeln und loszuwerden, die separate visited set.
Alternativ, wenn Sie eine benutzerdefinierte veränderlich Klasse / Struktur von Knoten können Sie speichern nur ein Boolesches flag, das in jedem Knoten, um anzuzeigen, ob es besucht haben, als Teil der aktuellen Suchpfad.Natürlich, diese Methode wird nicht lassen Sie die Ausführung der beiden sucht, auf der gleichen Kurve parallel dazu sollten Sie aus irgendeinem Grund tun wollen.
Hier einige test-code, die zeigen, wie die Funktion oben funktioniert:
# 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)
Dieser code ausgeführt, der auf dem gegebenen Beispiel-graph erzeugt die folgende Ausgabe:
A -> B -> C -> D A -> B -> D A -> C -> B -> D A -> C -> D
Beachten Sie, dass, obwohl dieses Beispiel ungerichteter graph ist (d.h.alle seine Kanten in beide Richtungen gehen), der Algorithmus funktioniert auch für beliebige gerichtete Graphen.Zum Beispiel, entfernen Sie die C -> B edge (durch entfernen B von der Nachbarin Liste C) ergibt die gleiche Ausgabe, außer der Dritte Weg (A -> C -> B -> D), das ist nicht mehr möglich.
Ps. Es ist leicht zu konstruieren Diagramme für die einfache such-algorithmen wie diese (und die anderen in diesem thread) auch sehr schlecht.
Betrachten Sie zum Beispiel die Aufgabe, die finden alle Pfade von A nach B auf einem ungerichteten Graphen, wo die Start-Knoten hat zwei Nachbarn:der Ziel-node B (die keine anderen Nachbarn, als A) und einen Knoten C das ist ein Teil eines clique von n+1 Knoten, wie diese:
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"),
}
Es ist leicht zu sehen, dass der einzige Pfad zwischen A und B ist die direkte, aber naive-DFS-angefangen von Knoten A zu verschwenden wird O(n!) Zeit nutzlos zu erforschen Wege innerhalb der clique, auch wenn es offensichtlich ist (für Menschen), dass keiner dieser Pfade können möglicherweise führen zu B.
Kann man auch konstruieren DAGs mit ähnlichen Eigenschaften, z.B.durch die Start-Knoten Eine Verbindung Zielknoten B und zwei anderen Knoten C1 und C2, die beide die Verbindung zum Knoten D1 und D2, die beide die Verbindung zum E1 und E2, und so weiter.Für n Schichten von Knoten so angeordnet, ein naiv-Suche für alle Pfade von A nach B wird am Ende verschwenden O(2n) die Zeit der Prüfung, die alle möglichen Sackgassen vor dem aufgeben.
Natürlich, das hinzufügen einer Kante, um die Ziel-Knoten B von einem Knoten in der clique (andere als C), oder von der letzten Schicht der DAG, würde erstellen Sie eine exponentiell große Anzahl von möglichen Pfaden von A nach B, und eine rein lokale-Suche-Algorithmus kann nicht wirklich sagen, im Voraus, ob Sie es finden so eine Kante ist oder nicht.Also in einem Sinn, den Armen Ausgang Empfindlichkeit der so naiv sucht, ist der Mangel an Bewusstsein für die Globale Struktur des Graphen.
Zwar gibt es verschiedene preprocessing-Methoden (wie die schrittweise Beseitigung der Blattknoten, die Suche nach single-node vertex Separatoren, etc.) , die verwendet werden könnten, zu vermeiden einige dieser "exponential-Zeit Sackgassen", ich weiß nicht, keine Allgemeine Vorverarbeitung trick eliminieren könnten Sie in alle Fällen.Eine Allgemeine Lösung wäre zu schauen, bei jedem Schritt der Suche, ob der Zielknoten ist weiterhin erreichbar (über einen sub-Suche), und backtrack früh, wenn es noch nicht — aber, ach, das wäre deutlich verlangsamen die Suche (im schlimmsten Fall proportional zu der Größe des Graphen) für viele Diagramme, nicht enthalten solche pathologischen Sackgassen.
Hier ist ein logisch besser aussehende rekursive version gegenüber in den zweiten Stock.
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);
}
}
}
}
Programm-Ausgang
B A C E
B A C F E
B E
B F C E
B F E
Lösung in C-code.Es basiert auf DFS verwendet (minimum) Speicher.
#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);
}
Ich habe entschieden ein ähnliches problem vor kurzem, und nicht alle Lösungen, die ich war nur daran interessiert, die kürzeste.
Ich benutzte eine "Breite zuerst" iterative Suche, die verwendet eine Warteschlange mit dem status' von denen jeder hielt einen Datensatz mit einem aktuellen Punkt auf der Kurve, und der Weg, der eingeschlagen wird, um dorthin zu gelangen.
Sie beginnen mit einem einzelnen Datensatz in der Warteschlange, die der Startknoten und einen leeren Pfad.
Jede iteration der code nimmt das Element aus dem Kopf der Liste und prüft, ob es eine Lösung (der Knoten angekommen ist, die Sie möchten, wenn es ist, wir sind fertig), sonst, es baut eine neue Warteschlange mit dem Knoten verbinden, um den aktuellen Knoten, und die geänderten Pfade basieren auf den Pfad der vorherigen Knoten, mit dem neuen jump befestigt am Ende.
Nun, könnten Sie etwas ähnliches, aber wenn man eine Lösung finden, anstatt zu stoppen, fügen Sie die Lösung zu Ihrem 'Liste' und fahren Sie Fort.
Sie müssen halten track von einem besuchten Knoten Liste, so dass Sie nie backtrack auf sich da Sie sonst eine unendliche Schleife.
wenn Sie möchten, dass ein bisschen mehr pseudocode schreiben Sie einen Kommentar oder etwas, und ich werde weiter.
Ich denke, Sie sollten beschreiben Sie Ihre wahre problem hinter dieser.Ich sage dies, weil du nach etwas Fragen, Zeit effiziente, aber die Antwort gesetzt, um das problem scheint exponentiell zu wachsen!
Daher würde ich nicht erwarten, einen besseren Algorithmus als etwas exponentiell.
Ich würde tun, backtracking und gehen durch das gesamte Diagramm.Um zu vermeiden, Zyklen, speichern Sie alle besuchten Knoten auf dem Weg.Wenn Sie zurück gehen, aufheben der Markierung des Knotens.
Mit Rekursion:
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
}
Oder ist das falsch?
edit:Oh, und ich vergaß:Sie sollten vermeiden, die rekursive Aufrufe durch die Nutzung dieser node-stack
Das Grundprinzip ist, Sie brauchen sich keine sorgen über Graphen.Dies ist die standard-problem, bekannt als Dynamische Konnektivität-problem.Es gibt folgende Arten von Methoden aus, die Sie erreichen können Knoten verbunden sind oder nicht:
- Schnellsuche
- Quick-Union
- Verbesserter Algorithmus (eine Kombination der beiden)
Hier ist Der C-Code, ich habe versucht, mit einem minimum an Zeit-Komplexität O(log*n), Dass heißt für 65536 Liste von Kanten, es erfordert 4 Suche und für 2^65536, Bedarf es 5 Suche.Ich Teile meine Implementierung des Algorithmus: Algorithmus Natürlich von der Princeton university
TIPP:Finden Sie Java-Lösung von link geteilt, die oben mit passenden Erklärungen.
/* 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;
}
Dies kann zu spät sein, aber hier ist die gleiche C# - version des DFS-Algorithmus in Java von Casey traverse für alle Pfade zwischen zwei Knoten mit einem stack.Die Lesbarkeit ist besser mit rekursiven wie immer.
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]
Diese Frage ist alt und bereits beantwortet.Doch keiner zeigen, vielleicht ein flexibler Algorithmus für die Erfüllung der gleichen Sache.Also werfe ich meinen Hut in den ring.
Ich persönlich finde einen Algorithmus der form find_paths[s, t, d, k] nützlich, wenn:
- s ist der Startknoten,
- t ist das Ziel-Knoten
- d ist die maximale Suchtiefe
- k ist die Anzahl der Pfade zu finden
Mit Hilfe der Programmiersprache form der Unendlichkeit für d und k geben Sie alle Pfade§.
§ natürlich, wenn Sie ein gerichteter graph, und Sie möchten, dass alle ungerichtete Wege zwischen s und t Sie haben diese beiden Möglichkeiten:
find_paths[s, t, d, k] <join> find_paths[t, s, d, k]
Hilfsfunktion
Ich persönlich mag die Rekursion, obwohl es als schwierig, einige Male, eh ersten lets definieren unsere Helfer-Funktion:
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()
Main-Funktion
Mit diesem aus dem Weg, die core Funktion ist trivial:
def find_paths[s, t, d, k]:
paths_found = [] # PASSING THIS BY REFERENCE
find_paths_recursion(s, t, 0, d, k, [], paths_found)
Erstens können feststellen, ein paar Sache:
- die oben genannten pseudo-code ist ein mash-up von Sprachen - aber die meisten stark ähneln python (da war ich gerade coding in it).Eine strenge copy-paste funktioniert nicht.
[]ist eine nicht initialisierte Liste, ersetzen Sie diese mit dem äquivalent für Ihre Programmiersprachepaths_foundübergeben wird Referenz.Es ist klar, dass die Rekursion Funktion nichts zurückgibt.Behandeln Sie diese angemessen.- hier
graphdie Annahme irgendeiner form derhashedStruktur.Es gibt eine fülle von Möglichkeiten zur Implementierung eines Graphen.Entweder Weg,graph[vertex]Sie bekommt eine Liste von benachbarten Scheitelpunkten in einem Regie Grafik - entsprechend anpassen. - dies setzt Voraus, Sie haben vor Verarbeitung zu entfernen "Schnallen" (self-loops), Zyklen-und multi-Kanten
Hier ist ein Gedanke aus der Spitze von meinem Kopf:
- Finden Sie eine Verbindung.(Depth-first-Suche ist wahrscheinlich ein guter Algorithmus für diese, da die Länge der Strecke spielt keine Rolle.)
- Deaktivieren Sie das Letzte segment.
- Versuchen, zu finden eine andere Verbindung aus den letzten Knoten vor den deaktivierten Anschluss.
- Springen 2, bis es nicht mehr verbindungen.
Soweit ich sagen kann, sind die Lösungen gegeben durch Ryan Fox (58343, Christian (58444), und sich selbst (58461) sind ungefähr so gut wie es bekommt.Ich glaube nicht, dass die Breite-zuerst-Traversierung hilft in diesem Fall, als Sie nicht alle Pfade.Zum Beispiel, mit Ecken und Kanten (A,B), (A,C), (B,C), (B,D) und (C,D) Sie erhalten Pfade ABD und ACD, aber nicht ABCD.
Ich fand einen Weg zum auflisten aller Pfade, einschließlich der unendlichen diejenigen mit loops.
http://blog.vjeux.com/2009/project/project-shortest-path.html
Finden Atomic Pfade & Zyklen
Definition
Was wir wollen zu tun ist, finden Sie alle möglichen Pfade gehen von Punkt A zu Punkt B.Da gibt es Zyklen beteiligt sind, können Sie nicht gehen Sie einfach durch und alle aufzuzählen.Stattdessen, Sie werden haben zu finden, atomic Weg, die nicht loop und die kleinste mögliche Zyklen (Sie nicht wollen, dass Ihr Zyklus wiederholt sich).
Die erste definition, die ich von einem atomaren Pfad ist ein Pfad, der nicht über die gleichen Knoten zweimal.Allerdings fand ich heraus, dass es nicht unter allen Möglichkeiten.Nach einiger überlegung habe ich herausgefunden, dass die Knoten nicht wichtig, aber die Ränder sind!So eine Atomare Pfad ist ein Pfad, der nicht gehen durch die gleiche Kante zweimal.
Diese definition ist praktisch, es funktioniert auch für Zyklen:eine Atomare Zyklus Ein Punkt ist eine unteilbare Weg, geht von Punkt A und endet um Punkt A.
Umsetzung
Atomic Paths A -> B
Um alle zu erhalten, der Pfad, ausgehend von Punkt A, wir sind gehen zu Durchlaufen des Graphen rekursiv von der Stelle A.Während man ein Kind ist, werden wir einen link child -> parent, um zu wissen, alle die Kanten haben wir bereits überschritten.Bevor wir gehen, das Kind, den wir durchqueren müssen, dass verknüpfte Liste, und stellen Sie sicher, dass das angegebene edge nicht bereits durchschritten.
Wenn wir kommen, um die Ziel Punkt, wir speichern kann der Pfad, den wir fanden.
Freeing the list
Ein problem tritt auf, wenn Sie möchten, um freie verknüpfte Liste.Es ist im Grunde ein Baum gekettet in umgekehrter Reihenfolge.Eine Lösung wäre, Doppel-link, Liste, und, wenn alle atomaren Wege gefunden worden, befreien Sie den Baum vom Ausgangspunkt aus.
Aber eine clevere Lösung ist die Verwendung eines "reference counting" (inspiriert von Garbage Collection).Jedes mal, wenn Sie eine Verknüpfung zu einem übergeordneten, die Sie Hinzugefügt zu Ihrer Referenz zählen.Dann, wenn Sie eintreffen am Ende einen Weg, Sie gehen rückwärts und frei, während der Referenzzähler gleich 1.Wenn es höher ist, müssen Sie nur entfernen und dann aufhören.
Atomic Cycle A
Auf der Suche für die Atomare Zyklus von A ist das gleiche wie auf der Suche für die Atomare Pfad von A nach A.Allerdings gibt es einige Optimierungen, die wir tun können.Erstens, wenn wir am Zielort angekommen zeigen wir speichern möchten den Pfad nur, wenn die Summe der Kanten Kosten ist negativ:wir wollen nur gehen durch absorbierende Zyklen.
Sie haben bereits gesehen, wird das gesamte Diagramm wird Durchlaufen, wenn Sie suchen für eine Atomare Pfad.Stattdessen können wir den Suchbereich einzugrenzen, um die starke zusammenhangskomponente mit A.Das Auffinden dieser Komponenten erfordert ein einfaches traversieren des Graphen mit Tarjan ' s Algorithmus.
Die Kombination von Atomaren Pfade und Zyklen
An diesem Punkt, wir haben alle die Atomare Wege, die geht von A nach B und alle atomaren Zyklen der einzelnen Knoten, Links, um uns zu organisieren, alles, um den kürzesten Weg.Von nun an werden wir studieren, wie zu finden die beste Kombination von Atom-Zyklen in eine Atomare Pfad.
Wie gekonnt beschrieben, indem einige der anderen Poster, die problem in a nutshell ist mit einem depth-first-search-Algorithmus rekursiv durchsuchen Sie die Graphen für alle Kombinationen von Pfaden zwischen den kommunizierenden Endpunkte.
Der Algorithmus selbst beginnt mit dem start-Knoten, der Sie es geben, untersucht alle seine ausgehenden links und schreitet durch die Erweiterung des ersten untergeordneten Knoten des Suchbaums, die angezeigt wird, suchen schrittweise tiefer und tiefer, bis der Zielknoten gefunden wird, oder bis es auf einen Knoten, der keine Kinder hat.
Die Suche dann backtracks, die Rückkehr zu den jüngsten Knoten, er ist noch nicht fertig, Sie zu erkunden.
Ich gebloggt über dieses Thema vor kurzem, buchen Sie ein Beispiel C++ Implementierung in die Prozess.
Hinzufügen von Casey Watson Antwort, hier ist eine andere Java-Implementierung.Initialisieren der besuchten Knoten mit dem start-Knoten.
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();
}
}
