algorithme pour un problème de graphe orienté

Question

S'il vous plaît aidez-moi un algorithme pour le problème suivant -

Compte tenu d'une collection de faits, nous aimerions vous débarrasser de redondance autant que possible. Les faits impliqués dans ce problème sont des membres d'une relation transitive entre majuscules. Donc chaque fait est une paire de lettres majuscules comme AB signifiant que A est apparenté à B. Une lettre peut ou non être liée à elle-même, mais la transitivité est vraie: si A est lié à B et B est lié à C alors on peut inférer que A est lié à C. Créer une classe FactCount qui contient une méthode minFacts qui reçoit une chaîne [] connue et qui renvoie la taille du plus petit ensemble de faits qui nous permettra de déduire tout (et seulement ces choses) cela peut être déduit des faits contenus dans connu.

Chaque élément de connu contiendra 1 ou plusieurs faits séparés par un seul espace. Le plus petit ensemble de faits peut contenir des faits qui peuvent être déduits de ceux qui sont connus mais qui n'y sont pas contenus.

Par exemple:

{ "AB AC CA AA BC", "AD"}

Retours: 4

AB, CA, BC et AD nous permettent de déduire les deux AA (AB, BC, CA donne AA par transitivité) et AC (AB, BC donne AC par transitivité), et il n'y a pas de sous-ensemble plus petit qui nous permet d'inférer tous les faits connus.

P.S - Ce n'est PAS un devoir. Juste un problème que j'ai trouvé en ligne et j'ai été incapable de résoudre pendant des heures ...

Answer 1

Il me semble que vous êtes à la recherche d'un spanning tree de votre graphique.

un arbre couvrant d'un graphe connexe G peut également être défini comme un maximum défini d'arêtes de G qui ne contient pas de cycle ou comme un ensemble minimal d'arêtes qui relient tous les sommets.

À partir de l'arborescence, vous avez une représentation minimale du graphique. Toute autre addition d'arêtes créera un cycle, et donc des informations redondantes pour les relations entre les nœuds. Notez également que si, à la fin de l'algorithme, vous avez des nœuds non connectés restants (ce qui signifie que certains nœuds de votre graphique ne touchent pas votre MST), cela signifie que l'arbre de recouvrement que vous avez obtenu est une entité indépendante, et il n'y a pas de relation (edge) reliant les nœuds de votre Spanning Tree et les nœuds qui n'y sont pas.

En termes plus mathématiques, les nœuds appartenant à votre arbre couvrant et les nœuds ne lui appartenant pas sont des ensembles disjoints, et aucun d'entre eux n'est l'ensemble vide.

Vous pouvez bien sûr effectuer à nouveau la recherche MST sur le sous-ensemble restant pour générer une forêt étendue, jusqu'à ce que vous épuisiez votre ensemble de nœuds. Pouvez-vous pointer vers un algorithme pour trouver le spanning tree minimum pour les graphes orientés?