Silne prepojené komponenty

Obsah

Kosarajuov algoritmus
Príklady jazyka Python, Java, C ++
Zložitosť Kosarajuovho algoritmu
Aplikácie silne prepojených komponentov

V tomto výučbe sa dozviete, ako sa tvoria silne spojené komponenty. Nájdete tiež pracovné príklady algoritmu kosararju v jazykoch C, C ++, Java a Python.

Silne spojená zložka je časť smerovaného grafu, v ktorej je cesta z každého vrcholu do iného. Je použiteľné iba na usmernený graf .

Napríklad:

Zoberme si nasledujúci graf.

Počiatočný graf

Silne spojené komponenty vyššie uvedeného grafu sú:

Silne spojené komponenty

Môžete pozorovať, že v prvej silne prepojenej zložke sa každý vrchol môže dostať na druhý vrchol nasmerovanou cestou.

Tieto komponenty možno nájsť pomocou Kosarajuovho algoritmu .

Kosarajuov algoritmus

Kosarajuov algoritmus je založený na algoritme hĺbkového prvého vyhľadávania, ktorý je implementovaný dvakrát.

Zahŕňajú sa tri kroky.

Najskôr vykonajte hĺbkové vyhľadávanie v celom grafe.
Začnime od vrcholu-0, navštívme všetky jeho podradené vrcholy a označené navštívené vrcholy označme ako splnené. Ak vrchol vedie k už navštívenému vrcholu, posuňte tento vrchol do stohu.
Napríklad: Počnúc vrcholom-0 choďte na vrchol-1, vrchol-2 a potom na vrchol-3. Vrchol-3 vedie k už navštívenému vrchole-0, preto zatlačte zdrojový vrchol (tj. Vrchol-3) do zásobníka. DFS v grafe
Prejdite na predchádzajúci vrchol (vrchol-2) a postupne navštívte jeho podradené vrcholy, tj. Vrchol 4, vrchol 5, vrchol 6 a vrchol 7. Pretože z vrcholu 7 nie je kam ísť, zatlačte ho do stohu. DFS na grafe
Prejdite na predchádzajúci vrchol (vrchol-6) a navštívte jeho podradené vrcholy. Ale všetky jeho podradené vrcholy sú navštívené, takže ho zatlačte do stohu. Stohovanie
Podobne sa vytvorí finálny stack. Final Stack
Obrátiť pôvodný graf. DFS na obrátenom grafe
Na obrátenom grafe vykonajte vyhľadávanie do hĺbky.
Začnite od najvyššieho vrcholu stohu. Prejdite všetky jeho podradené vrcholy. Po dosiahnutí už navštíveného vrcholu sa vytvorí jedna silne spojená zložka.
Napríklad: Pop vrchol-0 zo zásobníka. Počnúc vrcholom-0 prechádzajte jeho podradenými vrcholmi (vrchol-0, vrchol-1, vrchol-2, vrchol-3 v poradí) a označte ich ako navštívené. Dieťa vrcholu-3 je už navštívené, takže tieto navštívené vrcholy tvoria jednu silne prepojenú súčasť. Začnite zhora a prechádzajte cez všetky vrcholy
Prejdite na hromádku a vysuňte horný vrchol, ak už bol navštívený. V opačnom prípade vyberte vrcholový vrchol zo zásobníka a prechádzajte jeho podradenými vrcholmi, ako je uvedené vyššie. Ak je vrchol už otvorený, vysuňte ho Silne pripojený komponent
Silne spojené komponenty teda sú: Všetky silne spojené komponenty

Príklady jazyka 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(); )