Чврсто повезане компоненте

Преглед садржаја

Косарајуов алгоритам
Примери Питхон, Јава, Ц ++
Сложеност алгоритма Косарајуа
Чврсто повезане компоненте

У овом упутству ћете научити како се формирају чврсто повезане компоненте. Такође ћете наћи радне примере косарарјуовог алгоритма на Ц, Ц ++, Јава и Питхон.

Снажно повезана компонента је део усмереног графа у коме постоји пут од сваког темена до другог темена. Применљиво је само на усмереном графикону .

На пример:

Узмимо графикон испод.

Почетни графикон

Снажно повезане компоненте горњег графикона су:

Чврсто повезане компоненте

Можете приметити да у првој јако повезаној компоненти сваки врх може доћи до другог темена усмереним путем.

Ове компоненте се могу наћи помоћу Косарају-овог алгоритма .

Косарајуов алгоритам

Косарајуов алгоритам заснован је на алгоритму за претрагу дубине први пут имплементираном два пута.

Укључена су три корака.

Прво извршите претрагу дубине на целом графикону.
Кренимо од темена-0, посетимо све његове подређене врхове и означимо посећена темена као довршена. Ако врх води до већ посећеног темена, потисните овај врх у стек.
На пример: Полазећи од темена-0, пређите на тачку-1, тачку-2, а затим на тачку-3. Вертек-3 води до већ посећеног темена-0, па гурните изворни темен (тј. Вертек-3) у стек. ДФС на графикону
Идите на претходни врх (врх-2) и узастопно посетите његова подређена темена, тј. Темена-4, тачка-5, тачка-6 и тачка-7. Будући да се од врха-7 нема куда, гурните га у стек. ДФС на графикону
Идите на претходни врх (темен-6) и посетите његова подређена темена. Али, посећују се сви његови подређени врхови, па их гурните у хрпу. Слагање
Слично томе, креира се завршни стек. Финал Стацк
Обрни оригинални графикон. ДФС на обрнутом графикону
Извршите претрагу дубине на обрнутом графикону.
Почните од горњег темена стека. Пређите кроз све његове подрежене темене. Када се достигне већ посећени врх, формира се једна чврсто повезана компонента.
На пример: Поп вертек-0 из стека. Полазећи од темена-0, пређите преко његових подређених врхова (тачка-0, тачка-1, тачка-2, тачка-3 у низу) и означите их као посећене. Дијете темена-3 је већ посјећено, тако да ови посјећени врхови чине једну чврсто повезану компоненту. Почните од врха и пређите преко свих темена
Идите до стека и искочите горњи врх ако сте га већ посетили. У супротном, одаберите горњи врх из стека и пређите преко његових подређених врхова као што је горе приказано. Отворите горњи врх ако сте га већ посетили Чврсто повезана компонента
Дакле, чврсто повезане компоненте су: Све чврсто повезане компоненте

Примери Питхон, Јава, Ц ++

Питхон Јава Ц ++

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