Γράφοι (Graphs)

Ένας γράφος είναι μια δομή που αποτελείται από ένα σύνολο κορυφών ή κόμβων (nodes) και ένα σύνολο ακμών (edges) μεταξύ των κορυφών. Οι κορυφές θα μπορούσαν να είναι οι πόλεις μιας χώρας και οι ακμές οι δρόμοι που τις ενώνουν.

Mη-Κατευθυνόμενος Γράφος (undirected)
Mη-κατευθυνόμενος γράφος σημαίνει ότι οι ακμές του μπορεί να γραφτούν με διαφορετική σειρά. Π.χ. η ακμή (1,2) μπορεί να γραφτεί και ως (2,1).



Κατευθυνόμενος Γράφος (directed)
Ο γράφος πιο κάτω είναι κατευθυνόμενος που σημαίνει ότι οι ακμές του δεν μπορεί να γραφτούν με διαφορετική σειρά. Π.χ. η ακμή (1,2) δεν μπορεί να γραφτεί σαν (2,1).


Ο πιο πάνω είναι κατευθυνόμενος γράφος με 4 κορυφές (1, 2, 3, 4). Για να μεταβούμε από την κορυφή 1 στην κορυφή 4 δεν υπάρχει απευθείας ακμή, οπόταν πρέπει πρώτα να περάσουμε από την 2. Η ακολουθία των ακμών από τις οποίες περνάμε για να φτάσουμε στον τελικό προορισμό, λέγεται μονοπάτι (path). Το μονοπάτι από την κορυφή 1 στην κορυφή 4 συμβολίζεται με 1->2->4 και έχει μήκος 2 αφού αποτελείται από 2 ακμές. Δηλαδή, το μήκος ενός μονοπατιού είναι το πλήθος των ακμών του μονοπατιού.

Συνεκτικός Γράφος (connected): Ένας γράφος λέγεται συνεκτικός αν για κάθε δύο κορυφές του υπάρχει μονοπάτι που να τις συνδέει.
Κύκλος (cycle): Κύκλος σε ένα γράφο ονομάζεται μια διαδρομή που ξεκινά από ένα κόμβο και καταλήγει στον ίδιο κόμβο.


Με βάρη (weighted)
Σε ένα γράφο με βάρη, σε κάθε ακμή αντιστοιχεί ένα συγκεκριμένο βάρος ή κόστος (weight). Για κάθε μονοπάτι το κόστος θα είναι το σύνολο των βαρών που το αποτελούν. Στον πιο κάτω γράφο, για το μονοπάτι 1->2->3->4 το συνολικό κόστος θα είναι 1 + 2 + 2 = 5.


Δέντρο (Tree)
Ένας γράφος στον οποίο υπάρχει μονοπάτι μεταξύ δυο οποιωνδήποτε κορυφών, και δεν περιέχει κυκλικές διαδρομές, λέγεται δέντρο. Αναφερόμαστε στα στοιχεία του δέντρου ως κόμβους. Κάθε κόμβος συνδέεται με έναν ή περισσότερους κόμβους στους οποίους αναφερόμαστε, ως παιδιά του ή απόγονούς του. Οι κόμβοι που δεν έχουν απογόνους και βρίσκονται στο τελευταίο επίπεδο λέγονται φύλλα του δέντρου. Κάθε κόμβος έχει ακριβώς έναν πρόγονο, εκτός από τη ρίζα, που βρίσκεται συνήθως στην κορυφή του δέντρου.



Αναπαράσταση Γράφων

1. Πίνακας Γειτνίασης (Adjacency matrix)
Για την αναπαράσταση του γράφου χρησιμοποιούμε ένα τετραγωνικό πίνακα N x N (όπου N ο αριθμός των κόμβων) τα στοιχεία του οποίου είναι είτε 0 είτε 1 σύμφωνα με την εξής συνθήκη:  Αν η ακμή (i,j) ανήκει στο σύνολο των ακμών (αν υπάρχει ακμή που ενώνει τους κόμβους i και j) τότε A[i,j] = 1, αλλιώς A[i,j] = 0. Για μη-κατευθυνόμενους γράφους
ο πίνακας γειτνίασης θα είναι συμμετρικός ως προς την κύρια διαγώνιο λόγω του ότι αν υπάρχει η ακμή (i,j) τότε θα υπάρχει και η ακμή (j,i) αφού οι ακμές δεν δείχνουν φορά.


Κώδικας

Αρχείο εισόδου
6 7
6 4
4 3
4 5
5 2
3 2
5 1
2 1

2. Λίστα Γειτνίασης (Adjacency list)
Για την αναπαράσταση του γράφου χρησιμοποιούμε ένα vector μεγέθους n (όπου n ο αριθμός των κόμβων), τα στοιχεία του οποίου είναι άλλα vectors. Ο πίνακας είναι απλούστερος από την λίστα στην κωδικοποίηση, όμως η λίστα είναι πιο αποδοτική από τον πίνακα σε θέματα μνήμης και πολυπλοκότητας.


Κώδικας


Διάσχιση Γράφων (Graph Traversal)

Διάσχιση ενός γράφου είναι όταν επισκεπτόμαστε με κάποιο τρόπο όλους τους κόμβους ενός γράφου. Θα δούμε δύο τεχνικές με τις οποίες μπορούμε να το επιτύχουμε αυτό:


Ο αλγόριθμος του DFS έχει ως εξής:
  • Ξεκινούμε από ένα κόμβο (Α) και εξερευνούμε πλήρως έναν γείτονα του (Β)
  • Μετά συνεχίζουμε εξερευνώντας έναν από τους γείτονες του Β
  • Επαναλαμβάνουμε την ίδια διαδικασία αναδρομικά
  • Αποθηκεύουμε σε έναν πίνακα (visited) κατά πόσον έχουμε επισκεφτεί έναν κόμβο γιατί μόνο μια φορά χρειάζεται να επισκεφθούμε τον κάθε κόμβο
Κώδικας DFS (από πίνακα γειτνίασης)

Αρχείο εισόδου
12 11 1
1 2
2 3
3 4
3 5
2 6
1 7
1 8
8 9
8 12
9 10
9 11

Κώδικας DFS (από λίστα γειτνίασης)



Ο αλγόριθμος του BFS έχει ως εξής:
  • Ξεκινούμε από ένα κόμβο και εξερευνούμε όλους τους γείτονες του
  • Μετά συνεχίζουμε στους γείτονες των γειτόνων του
  • Αυτό γίνεται με την χρήση μιας ουράς (queue)
  • Επισκεπτόμαστε τον κόμβο στην αρχή της ουράς
  • Προσθέτουμε όλους τους γείτονες του που δεν έχουμε ήδη επισκεφτεί στο τέλος της ουράς
  • Συνεχίζουμε μέχρι να αδειάσει η ουρά, δηλαδή να έχουμε επισκεφτεί όλους τους κόμβους του γράφου

Κώδικας BFS (από πίνακα γειτνίασης)

Αρχείο εισόδου
12 11 1
1 2
2 3
3 4
3 5
2 6
1 7
1 8
8 9
8 12
9 10
9 11

Κώδικας ΒFS (από λίστα γειτνίασης)