Comment déterminer si deux noeuds sont connectés?

voix
13

Je crains que cela pourrait travailler sur un problème NP-complet. J'espère que quelqu'un peut me donner une réponse quant à savoir si elle est ou non. Et je suis à la recherche d'une réponse plus qu'un simple oui ou non. Je voudrais savoir pourquoi. Si vous pouvez dire, « Ceci est essentiellement ce problème « x » qui est / n'est pas NP-complet. (Lien wikipedia) »

(Non, ce n'est pas devoirs)

Y at-il un moyen de déterminer si deux points sont connectés sur un graphe arbitraire non dirigée. par exemple, les éléments suivants

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

Les points A si M (no « I ») sont des points de contrôle (comme une soupape dans une conduite de gaz naturel) qui peut être ouvert ou fermé. Les s « + » sont des noeuds (comme les tuyaux T de), et je suppose que le puits et la maison sont des nœuds aussi bien.

Je voudrais savoir si je ferme un point de contrôle arbitraire (par exemple, C) si le puits et la maison sont toujours connectés (autres points de contrôle peuvent également être fermés). Par exemple, si B, K et D sont fermés, nous avons encore un chemin à travers AEJFCGLM, et la fermeture C déconnectera le puits et la Chambre. Bien sûr; si juste D a été fermé, la fermeture ne C ne coupe pas la Chambre.

Une autre façon de mettre cela, est un bord C pont / supprimer / isthme?

Je peux traiter chaque point de contrôle comme un poids sur le graphe (soit 0 ouvert ou fermé pour 1); puis trouver le chemin le plus court entre le bien et la maison (un résultat> = 1 indiquerait qu'ils étaient déconnectés. Il y a différentes façons que je peux court-circuiter l'algorithme pour trouver le chemin le plus court aussi (par exemple, Rejeter un chemin une fois qu'il atteint 1, arrêt la recherche une fois que nous avons tout chemin qui relie le puits et la maison, etc.). et bien sûr, je peux aussi mettre dans une certaine limite artificielle sur le nombre de sauts pour vérifier avant d'abandonner.

Quelqu'un doit avoir classé ce genre de problème avant, je manque juste le nom.

Créé 09/12/2008 à 22:41
source utilisateur
Dans d'autres langues...                            


11 réponses

voix
31

Votre description semble indiquer que vous êtes simplement intéressé à savoir si deux noeuds sont connectés, ne pas trouver le chemin le plus court.

Trouver si deux noeuds sont connectés est relativement facile:

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.

Si vous utilisez une table de hachage ou quelque chose de similaire pour toDoSet et doneSet, je crois que c'est un algorithme linéaire.

Notez que cet algorithme est essentiellement la partie de marque de marquage et de balayage collecte des ordures.

Créé 09/12/2008 à 22:52
source utilisateur

voix
6

Voir http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm , un guichet unique pour tous les problèmes liés au graphique. Je crois que votre problème est en fait résoluble dans le temps du second degré.

Créé 09/12/2008 à 22:45
source utilisateur

voix
5

Vous n'avez pas besoin algorithme de Dijkstra pour ce problème, car il utilise un Heap qui n'est pas nécessaire et introduit un facteur de log (N) à votre complexité. Ceci est juste la largeur première recherche - ne comprennent pas les bords fermés comme bords.

Créé 09/12/2008 à 23:08
source utilisateur

voix
3

Le problème de trouver le chemin le plus court n'est pas NP-complet. Il est appelé le problème de Shortest Path (assez à l' origine) et il y a des algorithmes pour résoudre de nombreuses variantes différentes de celui - ci.

Le problème de déterminer si les deux noeuds sont connectés ne soit NP-complet. Vous pouvez utiliser une recherche en profondeur d'abord à partir de l'un des noeuds pour déterminer si elle est connectée à l'autre noeud.

Créé 09/12/2008 à 22:51
source utilisateur

voix
2

En supposant que vous avez une matrice de contiguïté:

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

Où bool [i, j] = true s'il y a un chemin ouvert entre i et j et bool [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;
}

Voici une version récursive de l'algorithme ci-dessus (écrit en 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
Créé 09/12/2008 à 23:23
source utilisateur

voix
2

Pour moi , il semble que vous êtes à une solution, mais il est possible d' avoir mal compris le problème. Si vous le faites comme vous dites, et donner les bords fermés 1 poids, vous pouvez appliquer simplement l'algorithme de Dijkstra, http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm . Cela devrait résoudre votre problème en O (E * lg (V))

Créé 09/12/2008 à 22:49
source utilisateur

voix
2

pas NP-complet, résolu avec une solution bien connue - l' algorithme de Dijkstra

Créé 09/12/2008 à 22:43
source utilisateur

voix
0

Je vois que vous avez votre réponse que c'est certainement pas NP-complet et c'est une question très ancienne aussi bien.

Cependant, je vais juste une autre approche propose de regarder le problème. Vous pouvez utiliser des ensembles disjoints pour cela. Dans la plupart des cas, pour le scénario donné, l'approche se traduira par un meilleur temps que de faire un parcours graphique (qui comprend la constante de temps pour une grande partie des tests). Cependant, la construction du graphique peut prendre une bonne quantité de temps, si l' union par la compression de rang ou le chemin est utilisé.

Vous pouvez lire sur la structure de données ici .

Créé 03/09/2018 à 13:36
source utilisateur

voix
0

Si tout ce que vous avez besoin est de déterminer si 2 noeuds sont connectés, vous pouvez utiliser des ensembles à la place, ce qui est plus rapide que les algorithmes de graphique.

  1. Divisez votre graphique entier dans les bords. Ajouter chaque bord à un ensemble.
  2. Sur l'itération suivante, tirer des bords entre les 2 noeuds externes du bord effectué à l'étape 2. Cela signifie que l'ajout de nouveaux noeuds (avec leurs ensembles correspondants) à l'ensemble du bord initial était de. (Fusion essentiellement set)
  3. Répétez 2 jusqu'à ce que les 2 noeuds que vous recherchez sont dans le même ensemble. Vous devrez également faire une vérification après l'étape 1 (juste au cas où les 2 noeuds sont adjacents).

Dans un premier temps vos nœuds seront chacun dans son ensemble,

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

Comme l'algorithme progresse et fusionne les ensembles, il divise par deux relativement l'entrée.

Dans l'exemple ci-dessus, je cherchais à voir s'il y avait un chemin entre o1 et o2. J'ai trouvé ce chemin seulement à la fin, après la fusion de tous bords. Certains graphiques peuvent avoir des composants séparés (déconnectés) qui implique que vous ne serez pas en mesure d'avoir un ensemble à la fin. Dans ce cas, vous pouvez utiliser cet algorithme pour tester la connectivité et même compter le nombre de composants dans un graphique. Le nombre de composants est le nombre de jeux que vous êtes en mesure d'obtenir lorsque l'algorithme se termine.

Un graphique possible (pour l'arbre ci-dessus):

o-o1-o-o-o2
  |    |
  o    o
       |
       o
Créé 17/12/2011 à 04:14
source utilisateur

voix
0

Dijkstra est surpuissant !! Il suffit d'utiliser la largeur première recherche de A à rechercher le nœud que vous souhaitez atteindre. Si vous ne trouvez pas, il est pas connecté. La complexité est O (nm) pour chaque recherche, qui est à moins de Dijkstra.

Plutôt connexe est le problème du flot maximal / min-cut. Regardez-le, il pourrait être pertinent à votre problème.

Créé 12/12/2008 à 15:11
source utilisateur

voix
-1

Tout graphe algorithme de chemin le plus court sera surpuissant si vous avez besoin est de trouver si un nœud est connecté à un autre. Une bonne bibliothèque Java qui accomplit qui est JGraphT . Son utilisation est très simple, voici un exemple d'un graphique entier:

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

Cette lib offre également tous les algorithmes les plus courts chemins aussi bien.

Créé 14/11/2016 à 06:34
source utilisateur

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