Comment faire pour déterminer si deux nœuds sont connectés?

Je suis inquiète de ce que cela pourrait être de travailler sur un problème NP-Complet de problème. J'espère que quelqu'un peut me donner une réponse quant à savoir s'il est ou pas. Et je suis à la recherche de plus d'une réponse que de simplement oui ou non. J'aimerais savoir pourquoi. Si vous pouvez dire,"C'est essentiellement ce problème" x " qui est/n'est pas NP-Complet. (lien wikipédia)"

(Non ce n'est pas de devoirs)

Est-il un moyen pour déterminer si les deux points sont reliés sur l'arbitraire d'un non-graphe orienté. par exemple, les suivantes

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

Points de A si M (pas de 'je') sont des points de contrôle (comme une soupape dans une conduite de gaz naturel) qui peut être ouvert ou fermé. Le '+'s sont des nœuds (comme le tuyau T), et je suppose que le Bien et la Maison sont aussi des nœuds.

Je voudrais savoir si je ferme l'arbitraire d'un point de contrôle (par exemple, C) si le Bien et de Maison sont toujours connecté (d'autres points de contrôle peut également être fermé). E. g., si B, K et D sont fermés, nous avons encore un chemin à travers les Un-E-J-F-C-G-L-M, et la fermeture de C débranchez le Puits et la Maison. Bien sûr; si D a été fermé, la fermeture ne C ne débranchez pas la Maison.

Un autre moyen de mettre cela, C est un pont/cut-edge/isthme?

J'ai pu traiter chaque point de contrôle comme un poids sur le graphique (soit 0 pour ouvrir ou de 1 à huis-clos); et ensuite trouver le chemin le plus court entre le Bien et de la Maison (suite >= 1 indique qu'ils ont été déconnectés. Il y a diverses façons de court-circuit de l'algorithme pour trouver le chemin le plus court (par exemple, jetez un chemin une fois qu'il atteint 1, arrêter la recherche, une fois que nous avons TOUT chemin qui relie le Puits et la Maison, etc.). Et bien sûr, je peux aussi le mettre dans certains artificielle limite sur le nombre de sauts à vérifier avant d'abandonner.

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

Êtes-vous sûr que vous êtes à la recherche pour le chemin le plus court? Il semble que vous voulez juste pour vérifier la connectivité. Connecteness est plus facile que le chemin le plus court.
Vous trouverez un exemple de code avec exemple & explications ici.
en.wikipedia.org/wiki/Connected_component_%28graph_theory%29

OriginalL'auteur BIBD | 2008-12-09