Wie Sie feststellen, ob zwei Knoten verbunden sind?

stimmen
13

Ich mache mir Sorgen, dass dies möglicherweise auf einem NP-vollständiges Problem arbeiten. Ich hoffe, jemand kann mir eine Antwort geben, ob es ist oder nicht. Und ich suche eher eine Antwort als nur ja oder nein. Ich möchte wissen, warum. Wenn Sie sagen: „Das ist im Grunde das Problem‚x‘, das ist / ist nicht NP-vollständig. (Wikipedia-Link)“

(Nein, das ist keine Hausaufgaben)

Gibt es eine Möglichkeit, um zu bestimmen, ob zwei Punkte auf einem beliebigen nicht-gerichteten Graphen verbunden sind. zB die folgenden

Well
  |
  |
  A
  |
  +--B--+--C--+--D--+
  |     |     |     |
  |     |     |     |
  E     F     G     H
  |     |     |     |
  |     |     |     |
  +--J--+--K--+--L--+
                    |
                    |
                    M
                    |
                    |
                  House

Die Punkte A, obwohl M (no ‚I‘) sind Steuerpunkte (wie ein Ventil in einem Erdgasrohr), die entweder offen oder geschlossen sein können. Die ‚+‘ s sind Knoten (wie Rohr-T-Shirts), und ich denke, das Gut und das Haus sind auch als auch Knoten.

Ich würde gerne wissen, ob ich einen beliebigen Kontrollpunkt geschlossen (zB C), ob das Gut und House sind immer noch verbunden (andere Kontrollpunkte auch geschlossen werden kann). Zum Beispiel, wenn B, K und D geschlossen sind, haben wir noch einen Weg durch AEJFCGLM und Schließen C wird das Gut und das Haus trennen. Na sicher; wenn nur wurden D, geschlossen Schließen nur C, das Haus nicht trennen.

Ein anderer Weg, dies zu setzen, ist C eine Brücke / Schnittkante / Isthmus?

Ich könnte jeden Steuerpunkt als Gewicht auf dem Graphen (entweder 0 oder 1 für offene für geschlossen) behandeln; und dann finden den kürzesten Weg zwischen Gut und Haus (ein Ergebnis> = 1 würde bedeuten, dass sie getrennt wurden. Es gibt verschiedene Möglichkeiten, wie ich kann der Algorithmus Kurzschluss für den kürzesten Weg zu finden, zu (zB einen Pfad verwerfen, sobald sie 1 erreicht, stoppen Benutzer, sobald wir einen beliebigen Pfad haben, der den Brunnen und das Haus, etc.). und natürlich verbindet, kann ich auch in einigen künstlichen Begrenzung setzen, wie viele Hops, bevor er aufgibt zu überprüfen.

Jemand muss diese Art von Problem, bevor eingestuft, ich bin nur der Name fehlt.

Veröffentlicht am 09/12/2008 um 22:41
quelle vom benutzer
In anderen Sprachen...                            


11 antworten

stimmen
31

Ihre Beschreibung scheint darauf hinzudeuten, dass Sie nur daran interessiert, ob zwei Knoten verbunden sind, nicht den kürzesten Weg zu finden.

wenn zwei Knoten zu finden, verbunden sind, ist relativ einfach:

Create two sets of nodes:  toDoSet and doneSet
Add the source node to the toDoSet 
while (toDoSet is not empty) {
  Remove the first element from toDoList
  Add it to doneList
  foreach (node reachable from the removed node) {
    if (the node equals the destination node) {
       return success
    }
    if (the node is not in doneSet) {
       add it to toDoSet 
    }
  }
}

return failure.

Wenn Sie eine Hash-Tabelle oder etwas ähnliches für toDoSet und doneSet verwenden, glaube ich, das ein linearer Algorithmus ist.

Beachten Sie, dass dieser Algorithmus im Grunde der Markierungsabschnitt der Speicherbereinigungs mark-and-Sweep ist.

Beantwortet am 09/12/2008 um 22:52
quelle vom benutzer

stimmen
6

Siehe http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm , Ihr One - Stop - Shop für alle Graphen Probleme. Ich glaube , Ihr Problem in der Tat auflösbar in quadratischer Zeit ist.

Beantwortet am 09/12/2008 um 22:45
quelle vom benutzer

stimmen
5

Sie brauchen nicht Dijkstra-Algorithmus für dieses Problem, da es einen Haufen verwendet, die nicht benötigt wird, und führt ein Faktor log (N), um Ihre Komplexität. Dies wird breite nur erste Suche - nicht die geschlossenen Kanten als Kanten aufweisen.

Beantwortet am 09/12/2008 um 23:08
quelle vom benutzer

stimmen
3

Das Problem , den kürzesten Weg zu finden , ist nicht NP-vollständig. Es ist die Shortest Path Problem (ursprünglich genug) genannt und es gibt Algorithmen für viele verschiedene Variationen davon zu lösen.

Das Problem der Bestimmung, ob zwei Knoten verbunden sind, ist nicht NP-vollständig entweder. Sie können eine Tiefensuche an jedem Knoten beginnend verwenden, um festzustellen, ob es mit dem anderen Knoten verbunden ist.

Beantwortet am 09/12/2008 um 22:51
quelle vom benutzer

stimmen
2

Unter der Annahme, dass Sie eine Adjazenzmatrix haben:

bool[,] adj = new bool[n, n];

Wo Bool [i, j] = true, wenn ein offener Weg zwischen i und j und Bool ist [i, i] = false.

public bool pathExists(int[,] adj, int start, int end)
{
  List<int> visited = new List<int>();
  List<int> inprocess = new List<int>();
  inprocess.Add(start);

  while(inprocess.Count > 0)
  {
    int cur = inprocess[0];
    inprocess.RemoveAt(0);
    if(cur == end)
      return true;
    if(visited.Contains(cur))
      continue;
    visited.Add(cur);
    for(int i = 0; i < adj.Length; i++)
      if(adj[cur, i] && !visited.Contains(i) && !inprocess.Contains(i))
        inprocess.Add(i);
  }
  return false;
}

Hier ist eine rekursive Version des Algorithmus oben (geschrieben in Ruby):

def connected? from, to, edges
  return true if from == to
  return true if edges.include?([from, to])
  return true if edges.include?([to, from])

  adjacent = edges.find_all { |e| e.include? from }
                  .flatten
                  .reject { |e| e == from }

  return adjacent.map do |a|
    connected? a, to, edges.reject { |e| e.include? from }
  end.any?
end
Beantwortet am 09/12/2008 um 23:23
quelle vom benutzer

stimmen
2

Mir scheint es , wie Sie auf zu einer Lösung sind, aber es ist möglich , dass ich das Problem falsch verstanden. Wenn Sie das tun , wie Sie sagen, und geben den geschlossenen Kanten 1 , wie Gewicht, können Sie einfach Dijkstra-Algorithmus anwenden, http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm . Dies sollte Ihr Problem in O (E * lg (V)) lösen

Beantwortet am 09/12/2008 um 22:49
quelle vom benutzer

stimmen
2

nicht NP-vollständig, mit einer bekannten Lösung gelöst - Dijkstra-Algorithmus

Beantwortet am 09/12/2008 um 22:43
quelle vom benutzer

stimmen
0

Ich sehe, Sie haben Ihre Antwort, dass es auf jeden Fall nicht NP-Complete und das ist eine sehr alte Frage, wie gut.

Allerdings werde ich vorschlagen , nur einen anderen Ansatz auf das Problem zu suchen. Sie könnten disjunkte Mengen für diese. In den meisten Fällen für das gegebene Szenario wird der Ansatz in einem besseren Zeit führen , als ein Graph Traversal tun (Das schließt konstante Zeit für einen großen Teil der Tests). Allerdings könnte nehmen Sie die Grafik Bau gute Zeit, wenn Vereinigung von Rang oder Pfad Kompression verwendet wird.

Sie können über die Datenstruktur lesen hier .

Beantwortet am 03/09/2018 um 13:36
quelle vom benutzer

stimmen
0

Wenn alles, was Sie brauchen, ist zu bestimmen, ob zwei Knoten verbunden sind Sie setzt stattdessen verwenden können, die schneller als Graphenalgorithmen ist.

  1. Teilen Sie Ihre gesamte Grafik in Kanten. Fügen jeder Kante mit einem Satz.
  2. Bei der nächsten Iteration ziehen Kanten zwischen den Knoten 2 Außen der Kante hergestellt in Schritt 2 Das bedeutet, Hinzufügen neuen Knoten (mit ihren entsprechenden Sätzen) an der die ursprüngliche Kante eingestellt war aus. (Grundsätzlich Verschmelzung eingestellt)
  3. Wiederholen Sie 2 bis in die 2-Knoten Sie suchen sind in den gleichen Satz. Sie werden auch (der 2-Knoten benachbart ist nur für den Fall) eine Überprüfung nach Schritt 1 tun müssen.

Zunächst Ihre Knoten wird jeder in seiner Menge,

o   o1   o   o   o   o   o   o2
 \ /     \ /     \ /     \ /
 o o     o o     o o     o o
   \     /         \     /
   o o o o         o o o o 
      \               /
       o o1 o o o o o o2

Da der Algorithmus fortschreitet und verschmilzt die Sätze Hälften es relativ die Eingabe.

Im Beispiel oben Ich war auf der Suche, um zu sehen, ob es ein Weg zwischen o1 und o2 war. Ich fand diesen Weg erst am Ende, nachdem alle Kanten verschmelzen. Einige Graphen haben können separate Komponenten (getrennt), das führt dazu, dass Sie nicht in der Lage sein werden, einen Satz am Ende zu haben. In einem solchen Fall können Sie diesen Algorithmus für Verbundenheit testen und auch die Anzahl der Komponenten in einem Diagramm zählen. Die Anzahl der Komponenten ist die Anzahl der Sätze Sie in der Lage sind, zu erhalten, wenn der Algorithmus beendet.

Ein mögliches Diagramm (für den Baum oben):

o-o1-o-o-o2
  |    |
  o    o
       |
       o
Beantwortet am 17/12/2011 um 04:14
quelle vom benutzer

stimmen
0

Dijkstra ist übertrieben !! Verwenden Sie einfach Breitensuche von A für den Knoten, den Sie erreichen wollen, zu suchen. Wenn Sie es nicht finden können, ist es nicht verbunden. Komplexität O (nm) für jede Suche, die weniger als Dijkstra ist.

Etwas verwandt ist das max-flow / min Schnittproblem. Schauen Sie es oben, könnte es für Ihr Problem relevant sein.

Beantwortet am 12/12/2008 um 15:11
quelle vom benutzer

stimmen
-1

Jeder Graph kürzesten Weg Algorithmus wird zu viel des Guten , wenn alles , was Sie brauchen , ist zu finden , wenn ein Knoten zu einem anderen verbunden ist. Eine gute Java - Bibliothek , die das erreicht ist JGraphT . Es ist Nutzung ist ganz einfach, hier ist ein Beispiel für ein Integer - Diagramm:

public void loadGraph() {
    // first we create a new undirected graph of Integers
    UndirectedGraph<Integer, DefaultEdge> graph = new SimpleGraph<>(DefaultEdge.class);

    // then we add some nodes
    graph.addVertex(1);
    graph.addVertex(2);
    graph.addVertex(3);
    graph.addVertex(4);
    graph.addVertex(5);
    graph.addVertex(6);
    graph.addVertex(7);
    graph.addVertex(8);
    graph.addVertex(9);
    graph.addVertex(10);
    graph.addVertex(11);
    graph.addVertex(12);
    graph.addVertex(13);
    graph.addVertex(14);
    graph.addVertex(15);
    graph.addVertex(16);

    // then we connect the nodes
    graph.addEdge(1, 2);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);
    graph.addEdge(3, 5);
    graph.addEdge(5, 6);
    graph.addEdge(6, 7);
    graph.addEdge(7, 8);
    graph.addEdge(8, 9);
    graph.addEdge(9, 10);
    graph.addEdge(10, 11);
    graph.addEdge(11, 12);
    graph.addEdge(13, 14);
    graph.addEdge(14, 15);
    graph.addEdge(15, 16);

    // finally we use ConnectivityInspector to check nodes connectivity
    ConnectivityInspector<Integer, DefaultEdge> inspector = new ConnectivityInspector<>(graph);

    debug(inspector, 1, 2);
    debug(inspector, 1, 4);
    debug(inspector, 1, 3);
    debug(inspector, 1, 12);
    debug(inspector, 16, 5);
}

private void debug(ConnectivityInspector<Integer, DefaultEdge> inspector, Integer n1, Integer n2) {
    System.out.println(String.format("are [%s] and [%s] connected? [%s]", n1, n2, inspector.pathExists(n1, n2)));
}

Diese lib bietet auch alle kürzesten Wege Algorithmen als auch.

Beantwortet am 14/11/2016 um 06:34
quelle vom benutzer

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more