Étant donné un graphe non orienté G = (V, E) , tel que u , v , w sont des arêtes de G.
Décrivez un algorithme pour déterminer si
"s'il y a un chemin de u à w qui passe par v"
Un algorithme simple pour cela utilisant DFS est donné ci-dessous:
bool checkFunction(){
graph g; // containing u, w, v
dfs(v);
if(isVisited(u) && isVisited(w))
return true;
else
return false;
}
Pour l'algorithme ci-dessus,
Mais pouvons-nous réduire la complexité du temps?
5 Réponses :
Une façon naïve de le faire est simplement de trouver tous les chemins que vous pouvez emprunter de u à w, puis de voir si v existe dans l'un de ces ensembles.
Ou simplement voir si un chemin existe de u à v et un chemin existe de v à w
Une bonne option mais ce sont des algorithmes très coûteux et ne sont pas optimisés. Cela prendra beaucoup d'espace et de temps dans des réseaux complexes.
Faites un BFS à partir de u . Arrêtez-le lorsque vous trouvez v .
Maintenant, faites un BFS à partir de v . Arrêtez-le lorsque vous trouvez w et renvoyez true .
Si vous ne trouvez pas v dans le premier BFS ou w dans le second BFS, cela signifie qu'il n'y a pas de chemin de u à w passant par v et vous pouvez arrêter le produit retournant false .
Complexité: O (| V | + | E |)
Sans plus de contraintes, il n'y a aucune optimisation disponible qui ne soit pas évidente.
Un chemin existe si u , v et w sont dans le même composant connecté. Cela peut être facilement déterminé en exécutant un BFS ou un DFS à partir de n'importe lequel pour voir s'il trouve les deux autres.
Pour certains graphes, il est possible de faire mieux lorsqu'un chemin n'existe pas et que l'un des sommets se trouve dans un petit composant connecté. Vous pouvez faire un seul BFS à partir de vos 3 sommets initiaux, et lorsque vous découvrez un nouveau sommet, rappelez-vous de quelle source il provient. Vous trouverez également des connexions lorsque vous découvrez une arête redondante, par exemple, d'un sommet u à un sommet v . Si vous manquez d'arêtes d'une source quelconque avant que les 3 ne soient connectées, vous pouvez vous arrêter, car vous savez que ce sommet est isolé.
Puisque le graphe n'est pas orienté, faites simplement un BFS à partir de w .
Cela garantit que si vous trouvez les chemins w->...->u et w->...->v , il y a aussi un chemin v->...->w->...->u , qui est également le chemin le plus court avec ces restrictions
À juste titre, pouvons-nous faire un bfs à partir de v & il visite à la fois u et w . Cela fonctionnerait aussi.
@superbrain Le titre dit explicitement: Determine whether there is a path from vertex **u to v passing through w**
@amit Ah, c'est vrai, le titre n'est pas d'accord avec le corps. Soupir. Pourquoi les gens font-ils ça ...
Remarque: cet article ne fournit pas de solution à la question posée, mais il fournit des informations sur les erreurs courantes que l'on peut faire en résolvant de tels problèmes.
(Cet article suppose également que les chemins ne permettent pas la duplication de sommets. Si vous supprimez cette contrainte, le problème peut être résolu facilement en trouvant un chemin de u à v, et un chemin de v à w et en concaténant simplement ces 2 chemins pour faire une promenade de u à w en passant par v. Cela peut être réalisé en exécutant BFS une fois à partir de u et une fois à partir de v)
La réponse donnée par amit n'est pas correcte.
Éditer:
L'exemple de compteur ci-dessous est incorrect, voir le commentaire de Steve. J'ai fourni un autre contre-exemple après celui-ci.
Prenons un contre-exemple.
V = {u, v, w, x}
E = {{u, v}, {u, w}, {u, x}, {v, x}, {w, x}}
Ensuite, le chemin (u, v, x, w) est un chemin valide.
Disons maintenant que nous appliquons BFS sur w, les chemins correspondants (non uniques) que nous obtenons de w à u et de w à v seront (w, u) et (w, u, v)
Maintenant, le "chemin" (v, u, w, u) a un nœud répété u, donc ce n'est pas un chemin.
Un autre contre-exemple:
Considérons V = {u, v, w, x, y, z} E = {{u, x}, {v, x}, {x, w}, {v, y}, {y, z}, { z, w}}
Un arbre BFS de w aura les arêtes {{w, x}, {w, z}, {x, u}, {x, v}} (nous traitons u, v comme des puits)
Cela donne le "chemin" {u, x, w, x, v} qui n'est pas valide
La réponse de Matt est également incorrecte.
Un chemin existe si u, v et w sont dans le même composant connecté.
Considérons un graphique linéaire {w, u, v}, alors tous ces 3 se trouvent dans le même composant connecté, mais il n'y a pas de chemin de u à w qui passe par v
Ce problème (pour les graphes non orientés) est également indiqué ici (voir le problème 7), qui je pense est une source fiable, nous pouvons donc supposer en toute sécurité qu'il existe un algorithme efficace pour cela.
Cela plaide également pour l'existence d'une solution et fournit un algorithme.
Pour les graphiques orientés, il s'agit d'un problème "difficile" .
Veuillez noter que cette réponse est en cours de discussion sur la méta dans Est-ce qu'une réponse qui dit que d'autres réponses sont fausses n'est pas une réponse? . Si vous avez une solution au problème, il serait très utile que vous l'ajoutiez à votre réponse ici :)
Annulez ceci parce que (A) il peut contenir des informations utiles, et (B) il est actuellement en cours de discussion sur Meta, et il est déraisonnable de discuter de la suppression d'une réponse quand cette réponse a déjà été supprimée par le mod. Si vous avez une opinion sur la raison pour laquelle cette réponse devrait ou ne devrait pas être supprimée, veuillez poster sur la question Meta à laquelle Scratte a lié (ne laissez pas de commentaire ici). Merci!
Je me demande si votre évaluation de la réponse de @ amit est erronée. (w, u, v) n'est-il pas exclu en tant que chemin en raison de la mise en garde qu'il déclare de traiter u et v comme des puits? Ainsi, le chemin de w à v serait (w, x, v) et le chemin final serait alors (v, x, w, u) , qui EST un chemin valide.
@Steve Vous avez raison, j'ai ajouté un autre contre-exemple en gardant la mise en garde à l'esprit
Le "Autre exemple de compteur" est également incorrect. Je ne sais pas pourquoi vous parlez du "chemin" {u, x, w, x, v}. La réponse dit seulement qu'il y a un chemin v->...->w->...->u , qui est correct (et il y a aussi un chemin u->...->v->...->w ). Btw, les exemples seraient beaucoup plus faciles à comprendre avec des images. De plus, faire en sorte que les gens passent par un exemple pour dire ensuite que c'est incorrect est plutôt impoli. Ne perdez pas le temps des gens.
@superbrain La question demande un moyen de trouver si un tel chemin existe, dans "un autre exemple de compteur" BFS peut prendre le chemin u, x, w, x, v, et signaler qu'il n'y a pas de chemin uvw (il y aura probablement nombre de ces contre-exemples). Quant à l'exemple incorrect, je ne sais pas si je dois le supprimer ou le laisser rester. J'ai vu des gens ici fournir un "Modifier" après avoir fait une erreur et depuis que Steve l'a corrigée, il est juste que je lui en attribue le mérite
Aussi, nous ne pouvons pas prétendre (pour les mêmes raisons) qu'un chemin de w vers u et un chemin de w vers v implique qu'il existe un chemin de v vers w vers u, puisque les chemins de w-> u et w-> v peut contenir des sommets communs
Comme vous l'avez montré, il trouverait les chemins w->...->u et w->...->v . Il conclurait donc qu'il existe également un chemin v->...->w->...->u , et cela se trouve être correct . Merci pour la modification, maintenant les personnes qui ne sont pas intéressées par cet exemple incorrect savent qu'elles peuvent l'ignorer.
"On conclurait donc qu'il y a aussi un chemin v -> ...-> w -> ...-> u" cela ne peut pas être conclu
Je "sais", mais il se trouve toujours que c'est correct. Notez que j'ai seulement dit que votre contre-exemple est incorrect, pas que leur réponse est correcte.
Mon contre-exemple utilise les mêmes étiquettes que la question. Renommez simplement les nœuds u comme v, w comme u et v comme w dans mon contre-exemple, puis vous obtenez le contre-exemple "correct" à l'étiquetage utilisé par la réponse acceptée
Votre contre-exemple pour Matt n'est pas nécessairement correct. Cela dépend si les nœuds en double sont autorisés sur le chemin. Comme le dit Wikipedia : "Certains auteurs n'exigent pas que tous les sommets d'un chemin soient distincts et utilisent plutôt le terme chemin simple pour désigner un tel chemin" . Et je n'ai même pas trouvé qu'en lisant l'article, je l'ai trouvé en ctrl-f-ing pour "simple" parce que je savais déjà à ce sujet (je pense que c'est en fait comme ça qu'on l'enseignait dans un cours universitaire que j'ai suivi). Donc, avec cette définition, la réponse de Matt est correcte .
La façon dont j'ai appris, les chemins qui permettent la répétition sont appelés promenades ( mathworld.wolfram.com/Walk.html ). Je suis d'accord que cela dépend de la convention, mais trouver une promenade uvw n'est pas un problème intéressant.
Pour votre argument "Ceci donne le" chemin "{u, x, w, x, v} qui n'est pas valide" , cet étiquetage n'est pas pertinent. Encore une fois: la réponse de Amit dit seulement qu'il ya un chemin. Pas à quoi ressemble un tel chemin. Et en effet, il y en a un, à savoir uxwzyv.
J'utiliserais simplement le graphique avec E = {{x, u}, {x, v}, {x, w}}, et j'affirmerais que je travaille sur l'hypothèse que "chemin" est censé ne pas autoriser les doublons .
dans un graphique linéaire {v, u, w}, il y a un chemin [u, v, u, w] qui passe par v. Il n'était pas nécessaire que les chemins soient simples. Aussi, vous devriez vraiment commenter ma réponse si vous voulez dire que c'est faux.
Pour une raison quelconque, vous supposez qu'un chemin avec des nœuds répétés n'est "pas un chemin". Ce n'est pas un chemin simple - mais c'est un chemin. La question ne demande pas de chemins simples. Ainsi, le contre-exemple que vous fournissez ne tient pas.
@amit Avez-vous pensé à ça de cette façon à l'époque, cependant? Quel était votre intérêt en traitant u et v comme des éviers?
@superbrain TBH, je ne me souviens pas. Leur faire des éviers pourrait probablement être simplement enlevé, et le rendre plus simple ...
@amit Pour moi, cela semblait être une tentative de recherche de chemins simples. Si vous avez le graphique linéaire wuv et que vous commencez à w et que vous vous arrêtez à u, alors vous ne trouverez pas v et conclurez à tort qu'il n'y a pas de chemin de u à v en passant par w. À moins que le chemin ne signifie un chemin simple.
@amit "Pour une raison quelconque, vous supposez qu'un chemin avec des nœuds répétés n'est" pas un chemin "" cela dépend de la convention. Selon Wikipédia (et de nombreux auteurs) ( en.wikipedia.org/wiki/Path_(graph_theory)#Walk,_trail,_path ), un chemin qui permet la répétition est appelé une "promenade"
Il existe de nombreux tutoriels sur Internet à ce sujet. Vous n'avez pas non plus fait d'efforts pour au moins initier la solution (c'est-à-dire en montrant ce que vous avez fait jusqu'à présent).
Tout d'abord, bienvenue à SO @AnupamKumar. Veuillez modifier pour ajouter des informations utiles comme des liens sur les techniques que vous connaissez déjà et que vous avez mentionnées; recherches que vous avez faites; et pourquoi pas un code reproductible minimal dans votre langage, pour que nous puissions également expérimenter, en fonction de votre approche initiale. Cela encouragera davantage de personnes à essayer de résoudre votre question.