Tugevalt ühendatud komponendid

Lang L: none (table-of-contents)

Kosaraju algoritm
Pythoni, Java, C ++ näited
Kosaraju algoritmi keerukus
Tugevalt ühendatud komponentide rakendused

Selles õpetuses saate teada, kui tugevalt ühendatud komponendid moodustuvad. Samuti leiate kosararju algoritmi toimivaid näiteid C, C ++, Java ja Python.

Tugevalt ühendatud komponent on suunatud graafi osa, kus igast tipust teise tippu kulgeb tee. See on rakendatav ainult suunatud graafikul .

Näiteks:

Võtame alloleva graafiku.

Esialgne graafik

Ülaltoodud graafiku tugevalt ühendatud komponendid on:

Tugevalt ühendatud komponendid

Võite täheldada, et esimeses tugevalt ühendatud komponendis võib iga tipp suunatud tee kaudu jõuda teise tipuni.

Need komponendid leiate Kosaraju algoritmist .

Kosaraju algoritm

Kosaraju algoritm põhineb kaks korda rakendatud sügavus-esimese otsingu algoritmil.

Kaasatud on kolm sammu.

Tehke kõigepealt kogu graafiku põhjal sügavusotsing.
Alustame tipust-0, külastame kõiki selle alamtiike ja märkime külastatud tipud tehtuks. Kui tipp viib juba külastatud tipuni, siis lükake see tipp virna.
Näiteks: alustades tipust 0, minge tippude 1, tipp-2 ja seejärel tippude 3 juurde. Tipp-3 viib juba külastatud tipp-0-ni, nii et lükake lähtetipp (st tipp-3) virna. DFS graafikul
Minge eelmisesse tippu (tipp-2) ja külastage järjestikku tema tippu, st tipp-4, tipp-5, tipp-6 ja tipp-7. Kuna tipust 7 pole kuhugi minna, lükake see virna. DFS graafikul
Minge eelmisele tipule (tipp-6) ja külastage selle lapsetippe. Kuid külastatakse kõiki selle alamtiike, nii et lükake see virna. Virnastamine
Samamoodi luuakse viimane virn. Viimane virn
Pöörake algne graafik ümber. DFS tagurpidi graafikul
Tehke tagurpidi graafikul sügavus-esimene otsing.
Alustage virna ülemisest tipust. Liikuge läbi kõigi selle alamtippude. Kui juba külastatud tipp on saavutatud, moodustub üks tugevalt ühendatud komponent.
Näiteks: hüpake tipp-0 virnast. Alustades tipust-0, liikuge läbi oma lapsetippude (tipp-0, tipp-1, tipp-2, tipp-3 järjestuses) ja märkige need külastatuks. Tipp-3 laps on juba külastatud, nii et need külastatud tipud moodustavad ühe tugevalt ühendatud komponendi. Alustage ülaosast ja läbige kõik tipud.
Minge virna ja hüpake ülemine tipp, kui seda juba külastate. Vastasel juhul valige virnast ülemine tipp ja liikuge selle allpool olevate tippude kaudu. Kui olete juba külastanud, avage ülemine tipp Tugevalt ühendatud komponent
Seega on tugevalt ühendatud komponendid järgmised: Kõik tugevalt ühendatud komponendid

Pythoni, Java, C ++ näited

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(); )