Wie bestimmt man, ob zwei Knoten miteinander verbunden sind?

Question

Ich mache mir Sorgen, dass dies an einem NP-vollständigen Problem arbeiten könnte. Ich hoffe, dass mir jemand eine Antwort geben kann, ob es das ist oder nicht. Und ich suche nach mehr als nur Ja oder Nein. Ich würde gerne wissen warum. Wenn Sie sagen können: "Dies ist im Grunde genommen das Problem 'x', das NP-vollständig ist/nicht ist. (Wikipedia-Link)"

(Nein, das ist keine Hausaufgabe)

Gibt es eine Möglichkeit festzustellen, ob zwei Punkte in einem beliebigen nicht gerichteten Graphen verbunden sind. z.B., der folgende

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

Die Punkte A bis M (kein 'I') sind Steuerpunkte (wie ein Ventil in einer Erdgasleitung), die entweder geöffnet oder geschlossen sein können. Die '+'s sind Knoten (wie Rohrgabelungen) und ich denke, der Brunnen und das Haus sind auch Knoten.

Ich möchte wissen, ob ich einen beliebigen Steuerpunkt schließe (z.B. C), ob der Brunnen und das Haus immer noch verbunden sind (andere Steuerpunkte können auch geschlossen sein). Z.B., wenn B, K und D geschlossen sind, haben wir immer noch einen Pfad über A-E-J-F-C-G-L-M und das Schließen von C würde den Brunnen und das Haus trennen. Natürlich wenn nur D geschlossen war, würde das Schließen von nur C das Haus nicht trennen.

Eine andere Möglichkeit, dies auszudrücken, ist C eine Brücke/Schnittkante/Isthmus?

Ich könnte jeden Steuerpunkt als Gewicht im Graphen behandeln (entweder 0 für geöffnet oder 1 für geschlossen) und dann den kürzesten Pfad zwischen Brunnen und Haus finden (ein Ergebnis >= 1 würde anzeigen, dass sie getrennt sind). Es gibt verschiedene Möglichkeiten, wie ich den Algorithmus zur Suche des kürzesten Pfades umgehen kann (z.B., einen Pfad verwerfen, sobald er 1 erreicht, die Suche stoppen, sobald wir einen beliebigen Pfad haben, der den Brunnen und das Haus verbindet, usw.). Und natürlich könnte ich auch eine künstliche Grenze festlegen, wie viele Sprünge zu überprüfen sind, bevor ich aufgebe.

Es muss jemand dieses Problem bereits klassifiziert haben, mir fehlt nur der Name.

Answer 1

Deine Beschreibung scheint darauf hinzuweisen, dass du nur daran interessiert bist, ob zwei Knoten verbunden sind, nicht daran, den kürzesten Pfad zu finden.

Zu finden, ob zwei Knoten verbunden sind, ist relativ einfach:

Erstelle zwei Sets von Knoten: toDoSet und doneSet
Füge den Ausgangsknoten zum toDoSet hinzu
während (toDoSet nicht leer ist) {
  Entferne das erste Element aus toDoSet
  Füge es zu doneSet hinzu
  für jeden (von dem entfernten Knoten erreichbaren Knoten) {
    wenn (der Knoten dem Zielknoten entspricht) {
       Erfolg zurückgeben
    }
    wenn (der Knoten nicht in doneSet ist) {
       füge ihn zu toDoSet hinzu
    }
  }
}

Rückgabe Fehler.

Wenn du für toDoSet und doneSet eine Hashtabelle oder etwas Ähnliches verwendest, handelt es sich meiner Meinung nach um einen linearen Algorithmus.

Beachte, dass dieser Algorithmus im Grunde genommen der Markierungsteil der Mark-und-Sweep-Garbage Collection ist.

Answer 2

Siehe http://de.wikipedia.org/wiki/Dijkstra-Algorithmus, Ihr One-Stop-Shop für alle graphenbezogenen Probleme. Ich glaube, Ihr Problem ist tatsächlich in quadratischer Zeit lösbar.

Answer 3

Sie benötigen den Dijkstra-Algorithmus nicht für dieses Problem, da er einen Heap verwendet, der nicht erforderlich ist und einen Faktor von log(N) zu Ihrer Komplexität einführt. Dies ist einfach eine Breitensuche - schließen Sie die geschlossenen Kanten nicht als Kanten ein.

Answer 4

Das Problem, den kürzesten Pfad zu finden, ist nicht NP-vollständig. Es wird als das kürzeste Pfadproblem (originell genug) bezeichnet und es gibt Algorithmen zur Lösung vieler verschiedener Varianten davon.

Das Problem zu bestimmen, ob zwei Knoten verbunden sind, ist ebenfalls nicht NP-vollständig. Sie können eine Tiefensuche starten, um zu bestimmen, ob ein Knoten mit einem anderen verbunden ist.

Answer 5

Unter der Annahme, dass Sie eine Adjazenzmatrix haben:

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

Wo bool[i,j] = true, wenn es einen offenen Pfad zwischen i und j gibt und bool[i,i] = false.

public bool pathExists(int[,] adj, int start, int end)
{
  List visited = new List();
  List inprocess = new List();
  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 obigen Algorithmus (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