Στόχοι εργαστηρίου:

Εξοικείωση με αναπαράσταση και αλγορίθμους σε γράφους Εξοικείωση με δομές union find Χρήστη της STL για τα παραπάνω

Γράφοι (απλοί)

• Ανατρέξτε στις διαφάνειες της διάλεξης 9 (αναπαράσταση γράφων) και με τη βοήθεια της STL αναπαραστείστε γράφο χωρίς βάρη

• Αναζητήστε στο διαδίκτυο πληροφορίες για τον κύκλο και το μονοπάτι Euler

• Αναζητήστε αλγόριθμο που να αποφαίνεται αν υπάρχει κύκλος ή μονοπάτι Euler σε ένα γράφο

• Υλοποιήστε την Άσκηση 11

• Ανατρέξτε στις διαφάνειες της διάλεξης 10 (διάσχιση γράφων) και εντοπίστε με ποιο τρόπο διάσχισης μπορούμε να εντοπίσουμε κύκλους σε ένα γράφο

• Υλοποιήστε την Άσκηση 12

Δομές Union - Find

• Ανατρέξτε στις διαφάνειες της διάλεξης 11 και υλοποιήστε μια δομή Union Find με τη βοήθεια της STL

• Υλοποιήστε την Άσκηση 13

Γράφοι (για προχωρημένους)

• Ανατρέξτε στις διαφάνειες της διάλεξης 9 (αναπαράσταση γράφων) και με τη βοήθεια της STL αναπαραστείστε γράφο με βάρη

• Καταστρώστε τον αλγόριθμο που ικανοποιεί τις απαιτήσεις της διάσχισης του γράφου που ζητάει η Άσκηση 14

• Καταγράψτε τις βοηθητικές δομές δεδομένων που απαιτούνται για να τηρείτε ενδιάμεσες πληροφορίες (π.χ. από διαδρομές που έχουν μερικώς εξεταστεί)

• Υλοποιήστε την Άσκηση 14