STERKT TILKOBLEDE KOMPONENTER - TECHCODEVIEW.COM

Strongly Connected Components (SCC-er) er et grunnleggende begrep innen grafteori og algoritmer. I en rettet graf, en Sterkt tilkoblet komponent er en delmengde av toppunkter der hvert toppunkt i delmengden kan nås fra alle andre toppunkter i samme delmengde ved å krysse de rettede kantene. Å finne SCCs av en graf kan gi viktig innsikt i strukturen og tilkoblingen til grafen, med applikasjoner innen ulike felt som f.eks. sosial nettverksanalyse, webcrawling og nettverksruting . Denne opplæringen vil utforske definisjonen, egenskapene og effektive algoritmene for å identifisere sterkt tilkoblede komponenter i grafdatastrukturer

string.compare c#

Innholdsfortegnelse

Hva er Strongly Connected Components (SCC-er)?
Hvorfor er SCC-er (Strongly Connected Components) viktige?
Forskjellen mellom tilkoblede og sterkt tilkoblede komponenter (SCC-er)
Hvorfor kan ikke konvensjonell DFS-metode brukes til å finne sterkt tilkoblede komponenter?
Koble til to sterkt koblede komponenter med en ensrettet kant
Brute Force-tilnærming for å finne sterkt tilkoblede komponenter
Effektiv tilnærming for å finne sterkt tilkoblede komponenter (SCC-er)

1. Kosarajus algoritme:
2. Tarjans algoritme:

Konklusjon

Hva er Strongly Connected Components (SCC-er)?

EN sterkt tilkoblet komponent av en rettet graf er en maksimal subgraf der hvert par av hjørner er gjensidig tilgjengelig. Dette betyr at for alle to noder A og B i denne undergrafen, er det en vei fra A til B og en vei fra B til A.

For eksempel: Grafen nedenfor har to sterkt sammenkoblede komponenter {1,2,3,4} og {5,6,7} siden det er vei fra hvert toppunkt til hvert annet toppunkt i den samme sterkt tilkoblede komponenten.

Sterkt tilkoblet komponent

Hvorfor er SCC-er (Strongly Connected Components) viktige?

Å forstå SCC-er er avgjørende for ulike applikasjoner som:

Nettverksanalyse : Identifisering av klynger av tett sammenkoblede noder.
Optimalisering av webcrawlere : Bestemme deler av webgrafen som er nært knyttet.
Avhengighetsoppløsning : I programvare, forstå hvilke moduler som er gjensidig avhengige.

Forskjellen mellom tilkoblede og sterkt tilkoblede komponenter ( SCCer)

Tilkobling i en urettet graf refererer til om to toppunkter er tilgjengelige fra hverandre eller ikke. To toppunkter sies å være forbundet hvis det er bane mellom dem. i mellomtiden Sterkt knyttet gjelder kun for rettet grafer . En undergraf i en rettet graf anses å være en Sterkt tilkoblede komponenter (SCC) hvis og bare hvis for hvert par av hjørner EN og B , det finnes en vei fra EN til B og en vei fra B til EN . La oss se hvorfor standard dfs-metode for å finne tilkoblede komponenter i en graf kan ikke brukes til å bestemme sterkt tilkoblede komponenter.

Tenk på følgende graf:

La oss nå starte en dfs ringe fra toppunkt 1 for å besøke andre toppunkter.

Hvorfor kan ikke konvensjonell DFS-metode brukes for å finne de sterkt tilkoblede komponentene?

Alle toppunktene kan nås fra toppunkt 1. Men toppunkt 1 og 5,6,7 kan ikke være i samme sterkt koblede komponent fordi det ikke er noen rettet vei fra toppunkt 5,6 eller 7 til toppunkt 1. Grafen har to sterkt sammenkoblede komponent tilkoblede komponenter {1,2,3,4} og {5,6,7}. Så den konvensjonelle dfs-metoden kan ikke brukes til å finne de sterkt tilkoblede komponentene.

fjær og fjær mvc

Koble til to sterkt koblede komponenter med en ensrettet kant

To forskjellige sammenkoblede komponenter blir en enkelt komponent hvis en kant legges til mellom et toppunkt fra en komponent til et toppunkt av en annen komponent. Men dette er ikke tilfelle i sterkt sammenkoblede komponenter. To sterkt koblede komponenter blir ikke en enkelt sterkt tilkoblet komponent hvis det bare er en ensrettet kant fra en SCC til en annen SCC.

formater dato til streng

unidrawio-(2)

Brute Force-tilnærming for å finne sterkt tilkoblede komponenter

Den enkle metoden vil være for hver toppunkt i (som ikke er en del av noen sterkt komponent) å finne toppunktene som vil være den delen av sterkt forbundet komponent som inneholder toppunkt i. To toppunkt i og j vil være i den samme sterkt sammenkoblede komponenten hvis de det er en rettet vei fra toppunkt i til toppunkt j og omvendt.

La oss forstå tilnærmingen ved hjelp av følgende eksempel:

Starter med toppunkt 1. Det er vei fra toppunkt 1 til toppunkt 2 og omvendt. På samme måte er det en vei fra toppunkt 1 til toppunkt 3 og omvendt. Så, toppunkt 2 og 3 vil være i den samme sterkt koblede komponenten som toppunkt 1. Selv om det er rettet bane fra toppunkt 1 til toppunkt 4 og toppunkt 5. Men det er ingen rettet vei fra toppunkt 4,5 til toppunkt 1, så toppunkt 4 og 5 vil ikke være i den samme sterkt tilkoblede komponenten som toppunkt 1. Dermed danner toppunkt 1,2 og 3 en sterkt tilkoblet komponent.
For Vertex 2 og 3 er Strongly Connected Component allerede bestemt.
For toppunkt 4 er det en bane fra toppunkt 4 til toppunkt 5, men det er ingen vei fra toppunkt 5 til toppunkt 4. Så toppunkt 4 og 5 vil ikke være i den samme sterkt tilkoblede komponenten. Så både Vertex 4 og Vertex 5 vil være en del av Single Strongly Connected Component.
Derfor vil det være 3 sterkt tilkoblede komponenter {1,2,3}, {4} og {5}.

Nedenfor er implementeringen av tilnærmingen ovenfor:

C++

 #include  using namespace std; class GFG { public:  // dfs Function to reach destination  bool dfs(int curr, int des, vector>& adj, vektor & vis) { // Hvis curr node er destinasjon 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;  } } } returner falsk;  } // For å fortelle om det er bane fra kilde til // destinasjon bool isPath(int src, int des, vektor>& adj) { vektor vis(adj.størrelse() + 1, 0);  return dfs(src, des, adj, vis);  } // Funksjon for å returnere alle de sterkt tilkoblede //-komponentene i en graf.  vektor> finnSCC(int n, vektor>& a) { // Lagrer alle de sterkt tilkoblede komponentene.  vektor> ans;  // Lagrer om et toppunkt er en del av en sterkt // Connected Component-vektor er_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> kanter{ { 1, 3 }, { 1, 4 }, { 2, 1 }, { 3, 2 }, { 4, 5 } };  vektor> ans = obj.finnSCC(V, kanter);  cout<< 'Strongly Connected Components are:
';  for (auto x : ans) {  for (auto y : x) {  cout << y << ' ';  }  cout << '
';  } }>

Java

 import java.util.ArrayList; import java.util.List; class GFG {  // dfs Function to reach destination  boolean dfs(int curr, int des, List> adj, Liste vis) { // Hvis curr node er destinasjon 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;  } } } returner falsk;  } // For å fortelle om det er sti fra kilden til // destinasjon boolean isPath(int src, int des, List> adj) { Liste 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> finnSCC(int n, Liste> a) { // Lagrer alle de sterkt tilkoblede komponentene.  Liste> ans = ny ArrayList();  // Lagrer om et toppunkt er en del av en hvilken som helst Strongly // Connected Component List is_scc = ny ArrayList(n + 1);  for (int i = 0; i<= n; i++) {  is_scc.add(0);  }  List> adj = ny ArrayList();  for (int i = 0; i<= n; i++) {  adj.add(new ArrayList());  }  for (List edge : a) { adj.get(edge.get(0)).add(edge.get(1));  } // Å krysse alle toppunktene for (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 = ny 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> edges = new ArrayList();  edges.add(ny ArrayList(List.of(1, 3)));  edges.add(ny ArrayList(List.of(1, 4)));  edges.add(ny ArrayList(List.of(2, 1)));  edges.add(ny ArrayList(List.of(3, 2)));  edges.add(ny ArrayList(List.of(4, 5)));  Liste> ans = obj.finnSCC(V, kanter);  System.out.println('Sterkt tilkoblede komponenter er:');  for (Liste x : ans) { for (int y : x) { System.out.print(y + ' ');  } System.out.println();  } } } // Denne koden er bidratt av shivamgupta310570>

Python

 class GFG: # dfs Function to reach destination def dfs(self, curr, des, adj, vis): # If current node is the destination, return True if curr == des: return True vis[curr] = 1 for x in adj[curr]: if not vis[x]: if self.dfs(x, des, adj, vis): return True return False # To tell whether there is a path from source to destination def isPath(self, src, des, adj): vis = [0] * (len(adj) + 1) return self.dfs(src, des, adj, vis) # Function to return all the strongly connected components of a graph. def findSCC(self, n, a): # Stores all the strongly connected components. ans = [] # Stores whether a vertex is a part of any Strongly Connected Component is_scc = [0] * (n + 1) adj = [[] for _ in range(n + 1)] for i in range(len(a)): adj[a[i][0]].append(a[i][1]) # Traversing all the vertices for i in range(1, n + 1): if not 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 part of this list. scc = [i] for j in range(i + 1, n + 1): # If there is a path from vertex i to vertex j and vice versa, # put vertex j into the current SCC list. if not is_scc[j] and self.isPath(i, j, adj) and self.isPath(j, i, adj): is_scc[j] = 1 scc.append(j) # Insert the SCC containing vertex i into the final list. ans.append(scc) return ans # Driver Code Starts if __name__ == '__main__': obj = GFG() V = 5 edges = [ [1, 3], [1, 4], [2, 1], [3, 2], [4, 5] ] ans = obj.findSCC(V, edges) print('Strongly Connected Components are:') for x in ans: for y in x: print(y, end=' ') print() # This code is contributed by shivamgupta310570>

 using System; using System.Collections.Generic; class GFG {  // dfs Function to reach destination  public bool Dfs(int curr, int des, List> adj, Liste vis) { // Hvis curr node er destinasjonen, return true if (curr == des) { return true;  } vis[curr] = 1;  foreach (var x i adj[curr]) { if (vis[x] == 0) { if (Dfs(x, des, adj, vis)) { return true;  } } } returner falsk;  } // For å fortelle om det er en sti fra kilde til destinasjon public bool IsPath(int src, int des, List> adj)  {  var vis = new List (adj.Tell + 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> FinnSCC(int n, Liste> a) { // Lagrer alle de sterkt tilkoblede komponentene var ans = new List>();  // Lagrer om et toppunkt er en del av en sterkt tilkoblet komponent 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> kanter = ny liste> { ny liste { 1, 3 }, ny liste { 1, 4 }, ny liste { 2, 1 }, ny liste { 3, 2 }, ny liste { 4, 5 } };  Liste> ans = obj.FinnSCC(V, kanter);  Console.WriteLine('Sterkt tilkoblede komponenter er:');  foreach (var x in ans) { foreach (var y in x) { Console.Write(y + ' ');  } Console.WriteLine();  } } } // Denne koden er bidratt av shivamgupta310570>

Javascript

 class GFG {  // Function to reach the destination using DFS  dfs(curr, des, adj, vis) {  // If the current node is the destination, return true  if (curr === des) {  return true;  }  vis[curr] = 1;  for (let x of adj[curr]) {  if (!vis[x]) {  if (this.dfs(x, des, adj, vis)) {  return true;  }  }  }  return false;  }  // Check whether there is a path from source to destination  isPath(src, des, adj) {  const vis = new Array(adj.length + 1).fill(0);  return this.dfs(src, des, adj, vis);  }  // Function to find all strongly connected components of a graph  findSCC(n, a) {  // Stores all strongly connected components  const ans = [];  // Stores whether a vertex is part of any Strongly Connected Component  const is_scc = new Array(n + 1).fill(0);  const adj = new Array(n + 1).fill().map(() =>[]);  for (la i = 0; i< a.length; i++) {  adj[a[i][0]].push(a[i][1]);  }  // Traversing all the vertices  for (let i = 1; i <= n; i++) {  if (!is_scc[i]) {  // If a vertex i is not part of any SCC,  // insert it into a new SCC list and check  // for other vertices that can be part of this list.  const scc = [i];  for (let 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] && this.isPath(i, j, adj) && this.isPath(j, i, adj)) {  is_scc[j] = 1;  scc.push(j);  }  }  // Insert the SCC containing vertex i into the final list.  ans.push(scc);  }  }  return ans;  } } // Driver Code Starts const obj = new GFG(); const V = 5; const edges = [  [1, 3], [1, 4], [2, 1], [3, 2], [4, 5] ]; const ans = obj.findSCC(V, edges); console.log('Strongly Connected Components are:'); for (let x of ans) {  console.log(x.join(' ')); } // This code is contributed by shivamgupta310570>

Produksjon

Strongly Connected Components are: 1 2 3 4 5>

Tidskompleksitet: O(n * (n + m)), fordi vi sjekker om det finnes en sti mellom dem for hvert par av hjørner.
Hjelpeområde: O(N)

overskrift i illustrator

Effektiv tilnærming for å finne sterkt tilkoblede komponenter (SCC-er)

For å finne SCC-er i en graf kan vi bruke algoritmer som Kosarajus algoritme eller Tarjans algoritme . La oss utforske disse algoritmene trinn for trinn.

1. Kosarajus algoritme :

Kosarajus algoritme involverer to hovedfaser:

Utføre Depth-First Search (DFS) på den originale grafen :
- Vi gjør først en DFS på den originale grafen og registrerer slutttidene for noder (dvs. tidspunktet da DFS er ferdig med å utforske en node fullstendig).
Utføre DFS på den transponerte grafen :
- Vi snur deretter retningen til alle kanter i grafen for å lage den transponerte grafen.
- Deretter utfører vi en DFS på den transponerte grafen, og tar i betraktning noder i synkende rekkefølge etter slutttider registrert i den første fasen.
- Hver DFS-gjennomgang i denne fasen vil gi oss én SCC.

Her er en forenklet versjon av Kosarajus algoritme:

DFS på originalgraf : Rekord slutttider.
Transponer grafen : Snu alle kanter.
DFS på transponert graf : Behandle noder i rekkefølge etter avtagende slutttider for å finne SCC-er.

2. Tarjans algoritme :

Tarjans algoritme er mer effektiv fordi den finner SCC-er i et enkelt DFS-pass ved å bruke en stabel og litt ekstra bokføring:

DFS Traversal : Under DFS, oppretthold en indeks for hver node og den minste indeksen (lav-lenkeverdi) som kan nås fra noden.
Stable : Hold styr på noder i rekursjonsstakken (en del av gjeldende SCC som utforskes).
Identifisering av SCC-er : Når en nodes lavlinkverdi er lik indeksen, betyr det at vi har funnet en SCC. Pop alle noder fra stabelen til vi når gjeldende node.

Her er en forenklet oversikt over Tarjans algoritme:

Initialiserindex>til 0.
Utfør DFS for hver ubesøkt node.
- Angi nodens indeks og lav-lenkeverdi.
- Skyv noden på stabelen.
- For hver tilstøtende node, utfør enten DFS hvis den ikke er besøkt eller oppdater lavlinkverdien hvis den er i stabelen.
- Hvis nodens lave lenkeverdi er lik dens indeks, skyver noder fra stabelen for å danne en SCC.

Konklusjon

Forstå og finne sterkt tilkoblede komponenter i en rettet graf er avgjørende for mange applikasjoner innen informatikk. Kosaraju sin og Tarjans Algoritmer er effektive måter å identifisere SCC-er på, hver med sin egen tilnærming og fordeler. Ved å mestre disse konseptene kan du bedre analysere og optimalisere strukturen og oppførselen til komplekse nettverk.