Міцно зв’язані компоненти

Зміст

Алгоритм Косарадзю
Приклади Python, Java, C ++
Складність алгоритму Косарадзю
Сильно пов'язані програми для компонентів

У цьому підручнику ви дізнаєтесь, як формуються міцно зв’язані компоненти. Крім того, ви знайдете робочі приклади алгоритму косарарю на C, C ++, Java та Python.

Сильно пов'язаною складовою є частина спрямованого графа, в якій є шлях від кожної вершини до іншої вершини. Він застосовується лише на спрямованому графіку .

Наприклад:

Візьмемо графік нижче.

Початковий графік

Сильно пов'язаними компонентами наведеного графіку є:

Міцно зв’язані компоненти

Ви можете помітити, що в першій сильно зв’язаній складовій кожна вершина може досягти іншої вершини через спрямований шлях.

Ці компоненти можна знайти за допомогою алгоритму Косараджу .

Алгоритм Косарадзю

Алгоритм Косарадзю базується на алгоритмі пошуку першої глибини, реалізованому двічі.

Задіяно три кроки.

Виконайте глибокий пошук спочатку на всьому графіку.
Почнемо з вершини-0, відвідаємо всі її дочірні вершини та позначимо відвідані вершини як виконані. Якщо вершина веде до вже відвіданої вершини, натисніть цю вершину до стеку.
Наприклад: Починаючи з вершини-0, перейдіть до вершини-1, вершини-2, а потім до вершини-3. Вершина-3 веде до вже відвіданої вершини-0, тому вставте вихідну вершину (тобто вершину-3) у стек. DFS на графіку
Перейдіть до попередньої вершини (вершини-2) і відвідайте її дочірні вершини, тобто вершину-4, вершину-5, вершину-6 та вершину-7 послідовно. Оскільки від вершини-7 нікуди подітися, засуньте її в стек. DFS на графіку
Перейдіть до попередньої вершини (вершини-6) і відвідайте її дочірні вершини. Але всі його дочірні вершини відвідуються, тому засуньте їх у стек. Укладання
Аналогічним чином створюється остаточний стек. Фінальний стек
Змінити початковий графік у зворотному напрямку. DFS на зворотному графіку
Виконайте пошук по глибині на зворотному графіку.
Почніть з верхньої вершини стека. Пройдіть усі його дочірні вершини. Після досягнення вже відвіданої вершини утворюється одна міцно зв’язана складова.
Наприклад: поп-вершина-0 зі стеку. Починаючи з вершини-0, пройдіть її дочірні вершини (вершина-0, вершина-1, вершина-2, вершина-3 послідовно) і позначте їх як відвідані. Нащадок вершини-3 вже відвіданий, тож ці відвідані вершини утворюють один тісно пов'язаний компонент. Почніть з верхньої частини та пройдіть по всіх вершинах.
Перейдіть до стеку та висуньте верхню вершину, якщо вона вже відвідана. В іншому випадку виберіть верхню вершину зі стеку та пройдіть її дочірні вершини, як показано вище. Висуньте верхню вершину, якщо її вже відвідали Міцно зв’язаний компонент
Отже, міцно зв’язаними компонентами є: Усі міцно зв’язані компоненти

Приклади 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(); )