. Connexion redondante-tutoriel php-php.cn

. Connexion redondante

Barbara Streisand

Libérer： 2025-01-30 08:04:39

original

685 Les gens l'ont consulté

684. Connexion redondante

Difficulté: moyen

Sujets: Recherche en profondeur, étendue première, recherche d'union, graphique

Dans ce problème, un arbre est un graphique non dirigé qui est connecté et n'a pas de cycles.

On vous donne un graphique qui a commencé comme un arbre avec n nœuds étiquetés de 1 à n, avec un bord supplémentaire ajouté. Le bord ajouté a deux vertices

différents choisis de 1 à n, et n'était pas un bord qui existait déjà. Le graphique est représenté comme un tableau des bords de la longueur n où les bords [i] = [a i _{, b} i _{] indiquent qu'il y a un bord entre les nœuds a} i _{et b} i _{dans le graphique.}

retourner

un bord qui peut être supprimé de sorte que le graphique résultant est un arbre de n nœuds . S'il y a plusieurs réponses, retournez la réponse qui se produit en dernier dans l'entrée .

Exemple 1:

. Connexion redondante

Entrée: EDGES = [[1,2], [1,3], [2,3]]
Sortie: [2,3]

Exemple 2:

. Connexion redondante

Entrée: EDGES = [[1,2], [2,3], [3,4], [1,4], [1,5]]
Sortie: [1,4]

Contraintes:

i _{& lt; b} i _{& lt; = edges.length}
i _{! = B} i

Solution:

Le problème

connexion redondante nous demande d'identifier un bord dans un graphique qui peut être supprimé pour transformer le graphique en arborescence valide. Un arbre est un graphique non dirigé qui est connecté et acyclique. On nous a donné un graphique qui a commencé comme un arbre mais a été modifié en ajoutant un bord supplémentaire. Notre objectif est de trouver et de retourner cet avantage supplémentaire.

Points clés

non dirigé et connecté .
dernier dans l'entrée, en cas de plusieurs solutions valides.

Approche

L'approche consiste à utiliser

la recherche en profondeur d'abord (DFS) pour détecter les cycles:

Représentation de la liste d'adjacence :
- Utilisez une liste d'adjacence pour représenter le graphique. Cette structure convient pour effectuer efficacement le DFS.
Détection du cycle via DFS :
- Avant d'ajouter un bord au graphique, utilisez DFS pour vérifier s'il y a déjà un chemin entre les deux sommets du bord. S'il y en a, l'ajout de ce bord formerait un cycle.
Renvoie le bord :
- Si un cycle est détecté, retournez le bord de courant comme connexion redondante.

Plan

Analyser les bords d'entrée.
Maintenez une liste d'adjacence pour suivre dynamiquement les connexions du graphique.
pour chaque bord:
- Utilisez une fonction DFS récursive pour vérifier si un chemin existe entre les deux sommets.
- Si un chemin existe, retournez le bord comme connexion redondante.
- Sinon, ajoutez le bord à la liste d'adjacence.
Renvoyez un résultat vide si aucun bord redondant n'est trouvé (bien que cela ne se produise pas selon les contraintes de problème).

implémentons cette solution dans PHP: 684. Connexion redondante

<?php /**
 * @param Integer[][] $edges
 * @return Integer[]
 */
function findRedundantConnection($edges) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to perform DFS and check connectivity
 *
 * @param $src
 * @param $target
 * @param $visited
 * @param $adjList
 * @return bool
 */
private function isConnected($src, $target, &$visited, &$adjList) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$edges1 = [[1,2],[1,3],[2,3]];
$edges2 = [[1,2],[2,3],[3,4],[1,4],[1,5]];

print_r(findRedundantConnection($edges1)) . "\n"; // Output: [2,3]
print_r(findRedundantConnection($edges2)) . "\n"; // Output: [1,4]
?>

Copier après la connexion

Explication:

Implémentation DFS :
- Commencez à partir d'un nœud et visitez récursivement ses voisins.
- Utilisez un tableau visité pour éviter de revisiter les nœuds.
- Si le nœud cible est atteint pendant la traversée, un chemin existe.
Addition de bord :
- Si aucun chemin n'existe entre les sommets du bord, ajoutez le bord à la liste d'adjacence et passez au bord suivant.
Edge redondant :
- Si un chemin existe déjà, renvoyez le bord actuel car il forme un cycle.

Exemple de procédure pas à pas

Exemple 1:

Entrée : EDGES = [[1, 2], [1, 3], [2, 3]]

étapes :

Initialiser la liste d'adjacence comme [].
traiter les bords:
- Ajouter [1, 2] → Graphique: {1: [2], 2: [1]}
- Ajouter [1, 3] → Graphique: {1: [2, 3], 2: [1], 3: [1]}
- Vérifier [2, 3]: DFS trouve un chemin → Retour [2, 3].

Sortie : [2, 3]

Exemple 2:

Entrée : bords = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]

étapes :

Initialiser la liste d'adjacence comme [].
traiter les bords:
- Ajouter [1, 2] → Graphique: {1: [2], 2: [1]}
- Ajouter [2, 3] → Graphique: {1: [2], 2: [1, 3], 3: [2]}
- Ajouter [3, 4] → Graphique: {1: [2], 2: [1, 3], 3: [2, 4], 4: [3]}
- Vérifier [1, 4]: DFS trouve un chemin → Retour [1, 4].

Sortie : [1, 4]

Complexité temporelle

DFS Traversal :
- Pour chaque bord, nous effectuons un DFS pour vérifier la connectivité.
- le pire des cas: o (v e) , où v est le nombre de sommets et e est le nombre de bords.
complexité totale :
- Puisque nous effectuons des DF pour chaque bord, la complexité globale est o (e × (v e)) .
Complexité spatiale :
- Liste d'adjacence: o (v e) .
- Array visité: o (v) .
- total: o (v e) .

Sortie pour des exemples

Exemple 1:

entrée : [[1, 2], [1, 3], [2, 3]]

sortie : [2, 3]

Exemple 2:

entrée : [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]

sortie : [1, 4]

Le problème peut être résolu efficacement en utilisant une approche basée sur une DFS pour détecter les cycles. Cette méthode construit dynamiquement le graphique et vérifie les bords redondants à chaque étape. La solution garantit l'exactitude en adhérant aux contraintes de problème et sort le bord qui forme un cycle et se produit en dernier dans l'entrée.

Contact Links

Si vous avez trouvé cette série utile, veuillez envisager de donner le dépositaire une étoile sur GitHub ou de partager le message sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi!

Si vous voulez un contenu plus utile comme celui-ci, n'hésitez pas à me suivre: