Ισχυρά συνδεδεμένα στοιχεία

Πίνακας περιεχομένων

Ο Αλγόριθμος του Kosaraju
Παραδείγματα Python, Java, C ++
Η πολυπλοκότητα του αλγόριθμου του Kosaraju
Εφαρμογές με ισχυρά συνδεδεμένα εξαρτήματα

Σε αυτό το σεμινάριο, θα μάθετε πώς σχηματίζονται ισχυρά συνδεδεμένα στοιχεία. Επίσης, θα βρείτε λειτουργικά παραδείγματα του αλγορίθμου kosararju σε C, C ++, Java και Python.

Ένα ισχυρά συνδεδεμένο στοιχείο είναι το τμήμα ενός κατευθυνόμενου γραφήματος στο οποίο υπάρχει μια διαδρομή από κάθε κορυφή προς μια άλλη κορυφή. Εφαρμόζεται μόνο σε κατευθυνόμενο γράφημα .

Για παράδειγμα:

Ας πάρουμε το παρακάτω γράφημα.

Αρχικό γράφημα

Τα ισχυρά συνδεδεμένα στοιχεία του παραπάνω γραφήματος είναι:

Ισχυρά συνδεδεμένα εξαρτήματα

Μπορείτε να παρατηρήσετε ότι στο πρώτο συστατικά που συνδέεται έντονα, κάθε κορυφή μπορεί να φτάσει στην άλλη κορυφή μέσω της κατευθυνόμενης διαδρομής.

Αυτά τα στοιχεία μπορούν να βρεθούν χρησιμοποιώντας τον Αλγόριθμο του Kosaraju .

Ο Αλγόριθμος του Kosaraju

Ο Αλγόριθμος του Kosaraju βασίζεται στον αλγόριθμο αναζήτησης βάθους-πρώτου που εφαρμόζεται δύο φορές.

Περιλαμβάνονται τρία βήματα.

Εκτελέστε μια πρώτη αναζήτηση βάθους σε ολόκληρο το γράφημα.
Ας ξεκινήσουμε από την κορυφή-0, να επισκεφτούμε όλες τις θυγατρικές κορυφές της και να επισημάνουμε τις κορυφές που έχετε επισκεφθεί ως ολοκληρωμένες. Εάν μια κορυφή οδηγεί σε μια ήδη επισκεμμένη κορυφή, σπρώξτε αυτήν την κορυφή στη στοίβα.
Για παράδειγμα: Ξεκινώντας από την κορυφή-0, μεταβείτε στην κορυφή-1, στην κορυφή-2 και στη συνέχεια στην κορυφή-3. Το Vertex-3 οδηγεί σε ήδη επισκεπτόμενη κορυφή-0, επομένως ωθήστε την κορυφή πηγής (δηλ. Κορυφή-3) στη στοίβα. DFS στο γράφημα
Μεταβείτε στην προηγούμενη κορυφή (κορυφή-2) και επισκεφθείτε τις θυγατρικές κορυφές της, δηλαδή την κορυφή-4, την κορυφή-5, την κορυφή-6 και την κορυφή-7 διαδοχικά. Επειδή δεν υπάρχει πουθενά από την κορυφή-7, σπρώξτε το στη στοίβα. DFS στο γράφημα
Μεταβείτε στην προηγούμενη κορυφή (κορυφή-6) και επισκεφθείτε τις θυγατρικές κορυφές της. Όμως, επισκέπτονται όλες τις θυγατρικές κορυφές του, οπότε σπρώξτε το στη στοίβα. Στοίβαγμα
Ομοίως, η τελική στοίβα δημιουργείται. Τελική στοίβα
Αντιστρέψτε το αρχικό γράφημα. DFS σε αντίστροφη γραφική παράσταση
Εκτελέστε αναζήτηση πρώτου βάθους στο αντίστροφο γράφημα.
Ξεκινήστε από την κορυφή κορυφής της στοίβας. Διασχίστε όλες τις θυγατρικές κορυφές του. Μόλις επιτευχθεί η ήδη επισκεπτόμενη κορυφή, σχηματίζεται ένα έντονα συνδεδεμένο στοιχείο.
Για παράδειγμα: Pop vertex-0 από τη στοίβα. Ξεκινώντας από την κορυφή-0, διασχίστε τις θυγατρικές κορυφές του (κορυφή-0, κορυφή-1, κορυφή-2, κορυφή-3 στη σειρά) και σημειώστε τις ως επισκέφθηκαν. Το παιδί της κορυφής-3 έχει ήδη επισκεφτεί, οπότε αυτές οι κορυφές που επισκέπτονται αποτελούν ένα έντονα συνδεδεμένο στοιχείο. Ξεκινήστε από την κορυφή και διασχίστε όλες τις κορυφές
Μεταβείτε στη στοίβα και ανοίξτε την κορυφαία κορυφή εάν έχετε ήδη επισκεφτεί. Διαφορετικά, επιλέξτε την κορυφή κορυφής από τη στοίβα και διασχίστε τις θυγατρικές κορυφές της όπως παρουσιάζονται παραπάνω. Εμφανίστε την κορυφή κορυφής εάν έχετε ήδη επισκεφτεί Ισχυρά συνδεδεμένο εξάρτημα
Έτσι, τα ισχυρά συνδεδεμένα στοιχεία είναι: Όλα τα ισχυρά συνδεδεμένα εξαρτήματα

Παραδείγματα Python, Java, C ++

Python Java C ++

 # Kosaraju's algorithm to find strongly connected components in Python from collections import defaultdict class Graph: def __init__(self, vertex): self.V = vertex self.graph = defaultdict(list) # Add edge into the graph def add_edge(self, s, d): self.graph(s).append(d) # dfs def dfs(self, d, visited_vertex): visited_vertex(d) = True print(d, end='') for i in self.graph(d): if not visited_vertex(i): self.dfs(i, visited_vertex) def fill_order(self, d, visited_vertex, stack): visited_vertex(d) = True for i in self.graph(d): if not visited_vertex(i): self.fill_order(i, visited_vertex, stack) stack = stack.append(d) # transpose the matrix def transpose(self): g = Graph(self.V) for i in self.graph: for j in self.graph(i): g.add_edge(j, i) return g # Print stongly connected components def print_scc(self): stack = () visited_vertex = (False) * (self.V) for i in range(self.V): if not visited_vertex(i): self.fill_order(i, visited_vertex, stack) gr = self.transpose() visited_vertex = (False) * (self.V) while stack: i = stack.pop() if not visited_vertex(i): gr.dfs(i, visited_vertex) print("") g = Graph(8) g.add_edge(0, 1) g.add_edge(1, 2) g.add_edge(2, 3) g.add_edge(2, 4) g.add_edge(3, 0) g.add_edge(4, 5) g.add_edge(5, 6) g.add_edge(6, 4) g.add_edge(6, 7) print("Strongly Connected Components:") g.print_scc()

 // Kosaraju's algorithm to find strongly connected components in Java import java.util.*; import java.util.LinkedList; class Graph ( private int V; private LinkedList adj(); // Create a graph Graph(int s) ( V = s; adj = new LinkedList(s); for (int i = 0; i < s; ++i) adj(i) = new LinkedList(); ) // Add edge void addEdge(int s, int d) ( adj(s).add(d); ) // DFS void DFSUtil(int s, boolean visitedVertices()) ( visitedVertices(s) = true; System.out.print(s + " "); int n; Iterator i = adj(s).iterator(); while (i.hasNext()) ( n = i.next(); if (!visitedVertices(n)) DFSUtil(n, visitedVertices); ) ) // Transpose the graph Graph Transpose() ( Graph g = new Graph(V); for (int s = 0; s < V; s++) ( Iterator i = adj(s).listIterator(); while (i.hasNext()) g.adj(i.next()).add(s); ) return g; ) void fillOrder(int s, boolean visitedVertices(), Stack stack) ( visitedVertices(s) = true; Iterator i = adj(s).iterator(); while (i.hasNext()) ( int n = i.next(); if (!visitedVertices(n)) fillOrder(n, visitedVertices, stack); ) stack.push(new Integer(s)); ) // Print strongly connected component void printSCC() ( Stack stack = new Stack(); boolean visitedVertices() = new boolean(V); for (int i = 0; i < V; i++) visitedVertices(i) = false; for (int i = 0; i < V; i++) if (visitedVertices(i) == false) fillOrder(i, visitedVertices, stack); Graph gr = Transpose(); for (int i = 0; i < V; i++) visitedVertices(i) = false; while (stack.empty() == false) ( int s = (int) stack.pop(); if (visitedVertices(s) == false) ( gr.DFSUtil(s, visitedVertices); System.out.println(); ) ) ) public static void main(String args()) ( Graph g = new Graph(8); g.addEdge(0, 1); g.addEdge(1, 2); g.addEdge(2, 3); g.addEdge(2, 4); g.addEdge(3, 0); g.addEdge(4, 5); g.addEdge(5, 6); g.addEdge(6, 4); g.addEdge(6, 7); System.out.println("Strongly Connected Components:"); g.printSCC(); ) )

 // Kosaraju's algorithm to find strongly connected components in C++ #include #include #include using namespace std; class Graph ( int V; list *adj; void fillOrder(int s, bool visitedV(), stack &Stack); void DFS(int s, bool visitedV()); public: Graph(int V); void addEdge(int s, int d); void printSCC(); Graph transpose(); ); Graph::Graph(int V) ( this->V = V; adj = new list(V); ) // DFS void Graph::DFS(int s, bool visitedV()) ( visitedV(s) = true; cout << s << " "; list::iterator i; for (i = adj(s).begin(); i != adj(s).end(); ++i) if (!visitedV(*i)) DFS(*i, visitedV); ) // Transpose Graph Graph::transpose() ( Graph g(V); for (int s = 0; s < V; s++) ( list::iterator i; for (i = adj(s).begin(); i != adj(s).end(); ++i) ( g.adj(*i).push_back(s); ) ) return g; ) // Add edge into the graph void Graph::addEdge(int s, int d) ( adj(s).push_back(d); ) void Graph::fillOrder(int s, bool visitedV(), stack &Stack) ( visitedV(s) = true; list::iterator i; for (i = adj(s).begin(); i != adj(s).end(); ++i) if (!visitedV(*i)) fillOrder(*i, visitedV, Stack); Stack.push(s); ) // Print strongly connected component void Graph::printSCC() ( stack Stack; bool *visitedV = new bool(V); for (int i = 0; i < V; i++) visitedV(i) = false; for (int i = 0; i < V; i++) if (visitedV(i) == false) fillOrder(i, visitedV, Stack); Graph gr = transpose(); for (int i = 0; i < V; i++) visitedV(i) = false; while (Stack.empty() == false) ( int s = Stack.top(); Stack.pop(); if (visitedV(s) == false) ( gr.DFS(s, visitedV); cout << endl; ) ) ) int main() ( Graph g(8); g.addEdge(0, 1); g.addEdge(1, 2); g.addEdge(2, 3); g.addEdge(2, 4); g.addEdge(3, 0); g.addEdge(4, 5); g.addEdge(5, 6); g.addEdge(6, 4); g.addEdge(6, 7); cout << "Strongly Connected Components:"; g.printSCC(); )