Passende algoritme om alle transitieve sluitingslussen in grafiek te vinden?

Ik wil alle transitieve sluitingslussen in mijn grafiek vinden met de volgende voorwaarden:

  1. als alle knooppunten die in de geïdentificeerde lus aanwezig zijn, een subset van een andere geïdentificeerde lus vormen, zullen we alleen superset overwegen.
  2. vind alle afzonderlijke lussen.

NOTE: read "loop" as--> transitive closure loop (i..e nodes in transitive closure set)

2
Uit je beschrijving lijkt het alsof je op zoek bent naar een algoritme voor het vinden van sterk verbonden componenten .
toegevoegd de auteur dasblinkenlight, de bron

1 antwoord

Gebruik Floyd-Warshall-algoritme alleen voor transitief onderdeel en controleer vervolgens of er sprake is van een reflexieve loops omdat transitieve lussen op het einde als reflexieve loops worden weergegeven.

0
toegevoegd