[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / raw/concept/kbhstrongly_connected_components.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "strongly connected components" source: https://www.jemoka.com/posts/kbhstrongly_connected_components/ --- strongly connected components expose local communities in a graph. constituents graph \(V,E\) requirements strongly connected: for all \(v,w \in V\), there is a path from \(v \to w\), and there’s a path for \(w \to v\). We can decompose a graph into strongly connected components where a subgraph is strongly connected. (i.e. they form equivalence class under “is strongly connected.”) additional information Kosaraju’s Algorithm A way to find strongly connected components in linear time \(O\qty(n+m)\). naive solution Use \(O\qty(n^{2})\) rounds to DFS from each node and check if the nodes are in a particular strongly connected component, or make a new one. why do we care? they tell you about communities in a graph structure some algorithms only make sense on SCCs (PageRank eigenvector centrality) condensation graph strongly connected components form a directed acyclic graph, which is useful for analysis. The condensation graph forms a DAG Proof idea: if there are edges both ways, there would be a way to go from each component to another and hence the SCC would collapse. finishing time: largest finish time of any element starting time: smallest starting time of any element