Silně propojené komponenty

Obsah

Kosarajuův algoritmus
Příklady Pythonu, Javy, C ++
Složitost Kosarajuova algoritmu
Silně propojené komponenty Aplikace

V tomto kurzu se dozvíte, jak jsou silně propojené komponenty formovány. Rovněž najdete funkční příklady algoritmu kosararju v jazycích C, C ++, Java a Python.

Silně spojená součást je část směrovaného grafu, ve které je cesta z každého vrcholu k jinému. Je použitelné pouze na směrovaný graf .

Například:

Vezměme si níže uvedený graf.

Počáteční graf

Silně propojené komponenty výše uvedeného grafu jsou:

Silně připojené komponenty

Můžete pozorovat, že v první silně propojené komponentě může každý vrchol dosáhnout nasměrované cesty na druhý vrchol.

Tyto komponenty lze najít pomocí Kosarajuova algoritmu .

Kosarajuův algoritmus

Kosarajuův algoritmus je založen na hloubkově prvním vyhledávacím algoritmu implementovaném dvakrát.

Jedná se o tři kroky.

Nejprve proveďte hloubkové vyhledávání v celém grafu.
Začněme od vrcholu-0, navštivte všechny jeho podřízené vrcholy a označte navštívené vrcholy jako hotové. Pokud vrchol vede k již navštívenému vrcholu, posuňte tento vrchol do zásobníku.
Například: Počínaje vrcholem-0 přejděte na vrchol-1, vrchol-2 a poté na vrchol-3. Vrchol-3 vede k již navštívenému vrcholu-0, proto zatlačte zdrojový vrchol (tj. Vrchol-3) do zásobníku. DFS v grafu
Přejít na předchozí vrchol (vrchol-2) a postupně navštívit jeho podřízené vrcholy, tj. Vrchol-4, vrchol-5, vrchol-6 a vrchol-7. Protože z vrcholu 7 není kam jít, zatlačte jej do hromádky. DFS v grafu
Přejít na předchozí vrchol (vrchol-6) a navštívit jeho podřízené vrcholy. Ale všechny jeho podřízené vrcholy jsou navštíveny, takže je zatlačte do zásobníku. Stohování
Podobně se vytvoří finální stoh. Final Stack
Obrátit původní graf. DFS na obráceném grafu
Na obráceném grafu proveďte vyhledávání do hloubky.
Začněte od horního vrcholu zásobníku. Projděte všechny podřízené vrcholy. Jakmile je dosaženo již navštíveného vrcholu, vytvoří se jedna silně spojená součást.
Například: Pop vrchol-0 ze zásobníku. Počínaje vrcholem 0 procházejte jeho podřízenými vrcholy (vrchol 0, vrchol 1, vrchol 2, vrchol 3 v pořadí) a označte je jako navštívené. Dítě vrcholu 3 je již navštíveno, takže tyto navštívené vrcholy tvoří jednu silně spojenou komponentu. Začněte shora a procházejte všemi vrcholy
Přejít na hromádku a vyskočit horní vrchol, pokud již byl navštíven. V opačném případě vyberte horní vrchol ze zásobníku a projděte jeho podřízenými vrcholy, jak je uvedeno výše. Pokud je již navštíven, vysuňte horní vrchol Silně připojená součástka
Silně propojené komponenty jsou tedy: Všechny silně spojené komponenty

Příklady Pythonu, Javy, 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(); )