Silně připojené komponenty (SCC) jsou základním konceptem v teorii grafů a algoritmech. V orientovaném grafu a Silně připojená součást je podmnožina vrcholů, kde každý vrchol v podmnožině je dosažitelný z každého druhého vrcholu ve stejné podmnožině procházením nasměrovaných hran. Nalezení SCC grafu může poskytnout důležité poznatky o struktuře a propojení grafu s aplikacemi v různých oblastech, jako je např analýza sociálních sítí, procházení webu a směrování sítě . Tento tutoriál prozkoumá definici, vlastnosti a účinné algoritmy pro identifikaci silně propojených komponent v grafových datových strukturách.

pawandeep rajan

Obsah

• Co jsou pevně připojené komponenty (SCC)?
• Proč jsou důležité pevně připojené komponenty (SCC)?
• Rozdíl mezi připojenými a pevně připojenými komponentami (SCC)
• Proč konvenční metodu DFS nelze použít k nalezení silně propojených komponent?
• Propojení dvou pevně propojených součástí jednosměrnou hranou
• Přístup hrubou silou pro nalezení pevně propojených součástí
• Efektivní přístup pro hledání silně propojených komponent (SCC)
• 1. Kosarajuův algoritmus:
• 2. Tarjanův algoritmus:
• Závěr

Co jsou pevně připojené komponenty (SCC)?

A silně propojená součást orientovaného grafu je maximální podgraf, kde je každá dvojice vrcholů vzájemně dosažitelná. To znamená, že pro libovolné dva uzly A a B v tomto podgrafu existuje cesta z A do B a cesta z B do A.

Například: Níže uvedený graf má dvě silně propojené komponenty {1,2,3,4} a {5,6,7}, protože existuje cesta z každého vrcholu do každého druhého vrcholu ve stejné silně propojené komponentě.

Silně připojená součást

Proč jsou důležité pevně připojené komponenty (SCC)?

Pochopení SCC je zásadní pro různé aplikace, jako jsou:

• Síťová analýza : Identifikace shluků těsně propojených uzlů.
• Optimalizace webových prohledávačů : Určení částí webového grafu, které spolu úzce souvisí.
• Řešení závislostí : V softwaru pochopení toho, které moduly jsou na sobě závislé.

Rozdíl mezi připojenými a pevně propojenými součástmi ( SCC)

Konektivita v a neorientovaný graf označuje, zda jsou dva vrcholy od sebe dosažitelné nebo ne. Říká se, že dva vrcholy jsou spojené, pokud mezi nimi existuje cesta. Mezitím Silně připojeno se vztahuje pouze na orientované grafy . Podgraf orientovaného grafu je považován za an Silně propojené komponenty (SCC) tehdy a jen tehdy pro každou dvojici vrcholů A a B , existuje cesta z A na B a cesta z B na A . Podívejme se, proč standardní metoda dfs k nalezení připojených komponent v grafu nelze použít k určení silně propojených složek.

Zvažte následující graf:

Rozvržení mřížky

Nyní začněme a dfs volání z vrcholu 1 k návštěvě jiných vrcholů.

Proč konvenční metoda DFS nemůže být použita k nalezení silně propojených komponent?

Všechny vrcholy lze dosáhnout z vrcholu 1. Ale vrcholy 1 a 5,6,7 nemohou být ve stejné silně propojené komponentě, protože neexistuje žádná směrovaná cesta z vrcholu 5,6 nebo 7 k vrcholu 1. Graf má dvě silně připojené komponenty {1,2,3,4} a {5,6,7}. Takže konvenční metoda dfs nemůže být použita k nalezení silně propojených komponent.

Propojení dvou pevně propojených součástí jednosměrnou hranou

Dvě různé spojené komponenty se stanou jedinou komponentou, pokud se mezi vrchol z jedné komponenty přidá hrana do vrcholu jiné komponenty. To ale není případ silně propojených komponent. Dvě silně propojené komponenty se nestanou jedinou pevně spojenou komponentou, pokud existuje pouze jednosměrná hrana z jednoho SCC k druhému SCC.

jméno

Přístup hrubou silou pro nalezení pevně propojených součástí

Jednoduchá metoda bude pro každý vrchol i (který není součástí žádné silně složené složky) najít vrcholy, které budou součástí silně spojené složky obsahující vrchol i. Dva vrcholy i a j budou ve stejné silně propojené komponentě, pokud existuje řízená cesta z vrcholu i do vrcholu j a naopak.

Pojďme pochopit přístup pomocí následujícího příkladu:

• Počínaje vrcholem 1. Existuje cesta z vrcholu 1 do vrcholu 2 a naopak. Podobně existuje cesta z vrcholu 1 do vrcholu 3 a naopak. Vrchol 2 a 3 tedy bude ve stejné silně propojené komponentě jako vrchol 1. Ačkoli existuje směrovaná cesta z vrcholu 1 do vrcholu 4 a vrcholu 5. Ale neexistuje žádná směrovaná cesta z vrcholu 4,5 do vrcholu 1, takže vrchol 4 a 5 nebudou ve stejné Silně připojené komponentě jako vrchol 1. Vertex 1,2 a 3 tedy tvoří Silně připojenou komponentu.
• Pro Vertex 2 a 3 již byla určena silně připojená komponenta.
• Pro Vertex 4 existuje cesta z vrcholu 4 do vrcholu 5, ale neexistuje žádná cesta z vrcholu 5 do vrcholu 4. Takže vrchol 4 a 5 nebudou ve stejné silně připojené komponentě. Vertex 4 i Vertex 5 tedy budou součástí Single Strongly Connected Component.
• Budou zde tedy 3 silně propojené komponenty {1,2,3}, {4} a {5}.

Níže je implementace výše uvedeného přístupu:

#include  using namespace std; class GFG { public:  // dfs Function to reach destination  bool dfs(int curr, int des, vector>& adj, vektor & vis) { // Pokud je curr node cíl, return true if (curr == des) { return true;  } vis[curr] = 1;  for (auto x : adj[curr]) { if (!vis[x]) { if (dfs(x, des, adj, vis)) { return true;  } } } return false;  } // Chcete-li zjistit, zda existuje cesta ze zdroje do // cíle bool isPath(int src, int des, vector>& adj) { vektor vis(adj.size() + 1, 0);  return dfs(src, des, adj, vis);  } // Funkce pro vrácení všech silně propojených // složek grafu.  vektor> findSCC(int n, vektor>& a) { // Uloží všechny silně propojené komponenty.  vektor> ans;  // Ukládá, zda je vrchol součástí jakéhokoli vektoru Silně // Připojené komponenty is_scc(n + 1, 0);  vektor> adj(n + 1);  for (int i = 0; i< a.size(); i++) {  adj[a[i][0]].push_back(a[i][1]);  }  // Traversing all the vertices  for (int i = 1; i <= n; i++) {  if (!is_scc[i]) {  // If a vertex i is not a part of any SCC  // insert it into a new SCC list and check  // for other vertices whether they can be  // thr part of thidl ist.  vector scc;  scc.push_back(i);  for (int j = i + 1; j<= n; j++) {  // If there is a path from vertex i to  // vertex j and vice versa put vertex j  // into the current SCC list.  if (!is_scc[j] && isPath(i, j, adj)  && isPath(j, i, adj)) {  is_scc[j] = 1;  scc.push_back(j);  }  }  // Insert the SCC containing vertex i into  // the final list.  ans.push_back(scc);  }  }  return ans;  } }; // Driver Code Starts int main() {  GFG obj;  int V = 5;  vector> hrany{ { 1, 3 }, { 1, 4 }, { 2, 1 }, { 3, 2 }, { 4, 5 } };  vektor> ans = obj.findSCC(V, hrany);  cout<< 'Strongly Connected Components are:
';  for (auto x : ans) {  for (auto y : x) {  cout << y << ' ';  }  cout << '
';  } }>

import java.util.ArrayList; import java.util.List; class GFG {  // dfs Function to reach destination  boolean dfs(int curr, int des, List> adj, Seznam vis) { // Pokud je uzel curr cíl, return true if (curr == des) { return true;  } vis.set(curr, 1);  for (int x : adj.get(curr)) { if (vis.get(x) == 0) { if (dfs(x, des, adj, vis)) { return true;  } } } return false;  } // Chcete-li zjistit, zda existuje cesta ze zdroje do // cíle boolean isPath(int src, int des, List> adj) { Seznam vis = new ArrayList(adj.size() + 1);  for (int i = 0; i<= adj.size(); i++) {  vis.add(0);  }  return dfs(src, des, adj, vis);  }  // Function to return all the strongly connected  // component of a graph.  List> findSCC(int n, Seznam> a) { // Uloží všechny silně propojené komponenty.  Seznam> ans = new ArrayList();  // Ukládá, zda je vrchol součástí jakéhokoli seznamu silně // připojených komponent is_scc = new ArrayList(n + 1);  for (int i = 0; i<= n; i++) {  is_scc.add(0);  }  List> adj = new ArrayList();  for (int i = 0; i<= n; i++) {  adj.add(new ArrayList());  }  for (List hrana : a) { adj.get(edge.get(0)).add(edge.get(1));  } // Procházení všech vrcholů pro (int i = 1; i<= n; i++) {  if (is_scc.get(i) == 0) {  // If a vertex i is not a part of any SCC  // insert it into a new SCC list and check  // for other vertices whether they can be  // the part of this list.  List scc = new ArrayList();  scc.add(i);  for (int j = i + 1; j<= n; j++) {  // If there is a path from vertex i to  // vertex j and vice versa, put vertex j  // into the current SCC list.  if (is_scc.get(j) == 0 && isPath(i, j, adj)  && isPath(j, i, adj)) {  is_scc.set(j, 1);  scc.add(j);  }  }  // Insert the SCC containing vertex i into  // the final list.  ans.add(scc);  }  }  return ans;  } } public class Main {  public static void main(String[] args) {  GFG obj = new GFG();  int V = 5;  List> hrany = new ArrayList();  edge.add(new ArrayList(List.of(1, 3)));  edge.add(new ArrayList(List.of(1, 4)));  edge.add(new ArrayList(List.of(2, 1)));  edge.add(new ArrayList(List.of(3, 2)));  edge.add(new ArrayList(List.of(4, 5)));  Seznam> ans = obj.findSCC(V, hrany);  System.out.println('Silně připojené součásti jsou:');  pro (Seznam x : ans) { for (int y : x) { System.out.print(y + ' ');  } System.out.println();  } } } // Tento kód přispěl shivamgupta310570>>>Krajta

using System; using System.Collections.Generic; class GFG {  // dfs Function to reach destination  public bool Dfs(int curr, int des, List> adj, Seznam vis) { // Pokud je cíl curr node, vrátí true if (curr == des) { return true;  } vis[curr] = 1;  foreach (var x in adj[curr]) { if (vis[x] == 0) { if (Dfs(x, des, adj, vis)) { return true;  } } } return false;  } // Chcete-li zjistit, zda existuje cesta od zdroje k cíli public bool IsPath(int src, int des, List> adj) { var show = nový seznam (přísl.počet + 1);  for (int i = 0; i< adj.Count + 1; i++)  {  vis.Add(0);  }  return Dfs(src, des, adj, vis);  }  // Function to return all the strongly connected components of a graph  public List> FindSCC(int n, Seznam> a) { // Uloží všechny silně propojené komponenty var ans = new List>();  // Ukládá, zda je vrchol součástí jakékoli silně připojené komponenty var isScc = new List (n + 1);  for (int i = 0; i< n + 1; i++)  {  isScc.Add(0);  }  var adj = new List>(n + 1);  for (int i = 0; i< n + 1; i++)  {  adj.Add(new List ());  } for (int i = 0; i< a.Count; i++)  {  adj[a[i][0]].Add(a[i][1]);  }  // Traversing all the vertices  for (int i = 1; i <= n; i++)  {  if (isScc[i] == 0)  {  // If a vertex i is not a part of any SCC  // insert it into a new SCC list and check  // for other vertices whether they can be  // the part of this list.  var scc = new List ();  scc.Add(i);  for (int j = i + 1; j<= n; j++)  {  // If there is a path from vertex i to  // vertex j and vice versa, put vertex j  // into the current SCC list.  if (isScc[j] == 0 && IsPath(i, j, adj) && IsPath(j, i, adj))  {  isScc[j] = 1;  scc.Add(j);  }  }  // Insert the SCC containing vertex i into  // the final list.  ans.Add(scc);  }  }  return ans;  } } // Driver Code Starts class Program {  static void Main(string[] args)  {  GFG obj = new GFG();  int V = 5;  List> hrany = nový seznam> { nový seznam { 1, 3 }, nový seznam { 1, 4 }, nový seznam { 2, 1 }, nový seznam { 3, 2 }, nový seznam { 4, 5 } };  Seznam> ans = obj.FindSCC(V, hrany);  Console.WriteLine('Silně připojené komponenty jsou:');  foreach (var x v ans) { foreach (var y v x) { Console.Write(y + ' ');  } Console.WriteLine();  } } } // Tento kód přispěl shivamgupta310570>>>Javascript

Strongly Connected Components are: 1 2 3 4 5>

Časová složitost: O(n * (n + m)), protože pro každý pár vrcholů kontrolujeme, zda mezi nimi existuje cesta.
Pomocný prostor: O(N)

večeře vs čas večeře

Efektivní přístup pro hledání silně propojených komponent (SCC)

K nalezení SCC v grafu můžeme použít algoritmy jako Kosarajuův algoritmus nebo Tarjanův algoritmus . Pojďme si tyto algoritmy prozkoumat krok za krokem.

1. Kosarajuův algoritmus :

Kosarajuův algoritmus zahrnuje dvě hlavní fáze:

1. Provádění hloubkového prvního vyhledávání (DFS) v původním grafu :
   • Nejprve provedeme DFS na původním grafu a zaznamenáme konečné časy uzlů (tj. čas, kdy DFS dokončí úplné prozkoumání uzlu).
2. Provádění DFS na transponovaném grafu :
   • Poté obrátíme směr všech hran v grafu, abychom vytvořili transponovaný graf.
   • Dále provedeme DFS na transponovaném grafu, vezmeme-li v úvahu uzly v sestupném pořadí podle jejich časů dokončení zaznamenaných v první fázi.
   • Každý průchod DFS v této fázi nám dá jeden SCC.

Zde je zjednodušená verze Kosarajuova algoritmu:

1. DFS na původním grafu : Zaznamenejte časy dokončení.
2. Transponujte graf : Obrácení všech hran.
3. DFS na transponovaném grafu : Zpracujte uzly v pořadí podle klesajících časů dokončení za účelem nalezení SCC.

2. Tarjanův algoritmus :

Tarjanův algoritmus je efektivnější, protože najde SCC v jediném průchodu DFS pomocí zásobníku a některého dalšího účetnictví:

1. DFS Traversal : Během DFS udržujte index pro každý uzel a nejmenší index (hodnota nízkého odkazu), kterého lze dosáhnout z uzlu.
2. Zásobník : Sledujte uzly, které jsou aktuálně v rekurzním zásobníku (část aktuálního SCC, která je prozkoumána).
3. Identifikace SCC : Když se hodnota nízkého odkazu uzlu rovná jeho indexu, znamená to, že jsme našli SCC. Vyberte všechny uzly ze zásobníku, dokud nedosáhneme aktuálního uzlu.

Zde je zjednodušený nástin Tarjanova algoritmu:

1. Inicializovatindex>na 0.
2. Pro každý nenavštívený uzel proveďte DFS.
   • Nastavte index uzlu a hodnotu nízkého odkazu.
   • Zatlačte uzel na stoh.
   • Pro každý sousední uzel buď proveďte DFS, pokud není navštíven, nebo aktualizujte hodnotu nízkého odkazu, pokud je v zásobníku.
   • Pokud se hodnota nízkého odkazu uzlu rovná jeho indexu, vysunou uzly ze zásobníku a vytvoří SCC.

Závěr

Pochopení a nalezení silně propojené komponenty v orientovaném grafu je zásadní pro mnoho aplikací v informatice. Kosaraju a Tarjanovi Algoritmy jsou účinnými způsoby identifikace SCC, z nichž každý má svůj vlastní přístup a výhody. Osvojením si těchto pojmů můžete lépe analyzovat a optimalizovat strukturu a chování komplexních sítí.