Soit N le nombre de sommets et M le nombre d'arêtes. Si vous voulez juste une solution O (NM) comme vous l'avez indiqué, vous n'avez pas besoin d'aller plus loin que d'exécuter un DFS pour chaque sommet.
La complexité pour chaque DFS est O (N + M), donc la complexité totale sera de O (N (N + M)) = O (N² + NM). Habituellement, nous avons plus d'arêtes que de sommets, donc NM croît beaucoup plus vite que N² et nous pouvons dire que la complexité est de O (NM). Gardez à l'esprit, cependant, que si vous supprimez physiquement le sommet actuel à chaque étape, votre implémentation sera beaucoup plus complexe, car la suppression physique d'un sommet signifie la suppression des entrées de nombreuses listes d'adjacence, ce qui coûte cher. graphique. Il existe une astuce d'implémentation pour accélérer le processus: au lieu de supprimer physiquement le sommet en cours avant chaque DFS, il suffit de marquer le sommet comme supprimé, et lorsque vous parcourez les listes d'adjacence pendant le DFS, ignorez simplement le sommet marqué. Cependant, je pense que vous pouvez résoudre ce problème en O (N + M) en utilisant l'algorithme de Tarjan pour trouver des points d'articulation. Cet algorithme trouvera chaque sommet qui, lorsqu'il est retiré du graphe, divise le graphe dans plus d'un composant connexe (ces sommets sont appelés points d'articulation). Il est facile de voir qu'il n'y aura pas de sommets isolés si vous supprimez un sommet qui n'est pas un point d'articulation. Cependant, si vous supprimez un point d'articulation, vous diviserez le graphe en deux parties G et G ', où G est la composante connexe du sommet de départ, et G' est le reste du graphe. Tous les sommets de G 'sont isolés car vous ne pouvez pas les atteindre si vous exécutez un DFS à partir du sommet de départ. Je pense que vous pouvez trouver la taille de G 'pour chaque suppression de vertex efficacement, peut-être que vous pouvez même le faire en exécutant Tarjan. Si je trouve une solution, je peux modifier cette réponse plus tard.
EDIT: j'ai réussi à résoudre le problème en O (N + M).Je vais donner quelques conseils afin que vous puissiez trouver la réponse par vous-même:
Chaque graphe non orienté peut être décomposé en (non disjoints) ensembles de composants biconnexes: chaque composant biconnexes est un sous-ensemble des sommets du graphe où chaque sommet de ce sous-ensemble restera connecté même si vous supprimez un sommet du graphique
L'algorithme O (N + M) de Tarjan pour trouver des ponts et des points d'articulation peut être modifié afin de trouver les composants biconnectés, trouver quels sommets appartiennent à chaque composant biconnecté, ou quels composants biconnectés contiennent chaque sommet
Si vous supprimez un sommet qui n'est pas un point d'articulation, réponse pour ce sommet est évidemment N-1
Si vous supprimez un point d'articulation, chaque sommet dans le même composant biconnexes du sommet de départ sera toujours accessible, mais vous ne connaissez pas les autres composants biconnectés. Ne vous inquiétez pas, il existe un moyen de trouver ceci efficacement
Vous pouvez compresser chaque graphe G dans un graphe B de ses composants biconnectés. L'algorithme de compression est simple: chaque composant biconnecté devient un sommet dans B, et vous liez des composants biconnectés qui partagent un point d'articulation. Nous pouvons prouver que le graphe B résultant est un arbre. Vous devez utiliser cet arbre en quelque sorte afin de résoudre le problème présenté à l'étape 4
Bonne chance!
Veuillez fournir un exemple concret. – Tempux