Εργαστήριο Τεχνολογίας Λογισμικού
0 votes
117 views

Στο μάθημα μιλήσαμε για τις Ισχυρές Συνεκτικές Συνιστώσες ενός γράφου και δώσαμε έναν αλγόριθμο εύρεσής τους. Κατά την υλοποίηση του, όμως, πρόκυπτει το ερώτημα του πώς θα περιγραφόυν οι Ισχυρές Συνεκτικές Συνιστώσες (aka τι θα επιστρέφει ο αλγόριθμος).

Έχω σκεφτεί 2 λύσεις:
1. Με μια λίστα από λίστες, όπου κάθε υπολίστα είναι μια Ισχυρά Συνεκτική Συνιστώσα. (όπου λίστα μπορούμε να βάλουμε όποιο container επιθυμούμε).
2. Με έναν γράφο όπου κάθε κόμβος είναι ένας γράφος, που είναι μια Ισχυρά Συνεκτική Συνιστώσα.
Η μεν 1η λύση χάνει την πληροφορία του τρόπου σύνδεσης των Συνιστώσεων (δηλαδή δεν γνωρίζουμε ποια είναι η πηγή και η καταβόθρα Συνιστώσα), ενώ η δε 2η λύση χάνει τον κόμβο σύνδεσης των συνιστώσεων.

Τελικά, στην πράξη πώς περιγράφονται οι Ισχυρά Συνεκτικές Συνιστώσες;

in progtech by (2.9k points) | 117 views
0

Υποθέτω θα αποθήκευες μαζί με τον αρχικό γράφο την λίστα/γράφο με τα SCC οπότε δε θα υπήρχαν αυτά τα προβλήματα. Στην 2η περίπτωση του γραφου θα μπορούσες σε κάθε γραφο/scc να αποθηκεύεις ξεχωριστά σε μια λίστα τις ακμές/κομβους συνδεσης.

Please log in or register to answer this question.

264 questions

256 answers

274 comments

2.9k users