STARKT ANSLUTNA KOMPONENTER - TECHCODEVIEW.COM

Starkt anslutna komponenter (SCC) är ett grundläggande begrepp inom grafteori och algoritmer. I en riktad graf, en Starkt ansluten komponent är en delmängd av hörn där varje vertex i delmängden kan nås från alla andra hörn i samma delmängd genom att korsa de riktade kanterna. Att hitta SCCs av en graf kan ge viktiga insikter om grafens struktur och anslutningsmöjligheter, med tillämpningar inom olika områden som t.ex. sociala nätverksanalyser, webbcrawlning och nätverksrouting . Denna handledning kommer att utforska definitionen, egenskaperna och effektiva algoritmerna för att identifiera starkt anslutna komponenter i grafdatastrukturer

Madhubala

Innehållsförteckning

Vad är Strongly Connected Components (SCC)?
Varför är starkt anslutna komponenter (SCC) viktiga?
Skillnaden mellan anslutna och starkt anslutna komponenter (SCC)
Varför kan en konventionell DFS-metod inte användas för att hitta starkt anslutna komponenter?
Ansluta två starkt anslutna komponenter med en enkelriktad kant
Brute Force Approach för att hitta starkt anslutna komponenter
Effektivt tillvägagångssätt för att hitta starkt anslutna komponenter (SCC)

1. Kosarajus algoritm:
2. Tarjans algoritm:

Slutsats

Vad är Strongly Connected Components (SCC)?

A starkt ansluten komponent av en riktad graf är en maximal subgraf där varje par av hörn är ömsesidigt nåbart. Detta betyder att det för två noder A och B i denna subgraf finns en väg från A till B och en väg från B till A.

Till exempel: Grafen nedan har två starkt anslutna komponenter {1,2,3,4} och {5,6,7} eftersom det finns en väg från varje vertex till varannan vertex i samma starkt anslutna komponent.

Starkt ansluten komponent

Varför är starkt anslutna komponenter (SCC) viktiga?

Att förstå SCC är avgörande för olika applikationer som:

Nätverksanalys : Identifiera kluster av tätt sammankopplade noder.
Optimera webbsökare : Bestämma delar av webbgrafen som är nära sammanlänkade.
Beroendeupplösning : I programvara, förstå vilka moduler som är beroende av varandra.

Skillnaden mellan anslutna och starkt anslutna komponenter ( SCCs)

Anslutning i en oriktad graf hänvisar till om två hörn kan nås från varandra eller inte. Två hörn sägs vara sammankopplade om det finns väg mellan dem. Under tiden Starkt ansluten gäller endast för riktade grafer . En subgraf i en riktad graf anses vara en Starkt anslutna komponenter (SCC) om och bara om för varje par av hörn A och B , det finns en väg från A till B och en väg från B till A . Låt oss se varför standard dfs-metod för att hitta anslutna komponenter i en graf kan inte användas för att bestämma starkt anslutna komponenter.

Tänk på följande graf:

Nu, låt oss börja a dfs ring från vertex 1 för att besöka andra hörn.

Varför kan en konventionell DFS-metod inte användas för att hitta de starkt anslutna komponenterna?

Alla hörn kan nås från vertex 1. Men hörn 1 och 5,6,7 kan inte vara i samma starkt sammankopplade komponent eftersom det inte finns någon riktad väg från vertex 5,6 eller 7 till vertex 1. Grafen har två starkt anslutna komponenter {1,2,3,4} och {5,6,7}. Så den konventionella dfs-metoden kan inte användas för att hitta de starkt anslutna komponenterna.

mysql unik nyckel

Ansluta två starkt anslutna komponenter med en enkelriktad kant

Två olika sammankopplade komponenter blir en enda komponent om en kant läggs till mellan en vertex från en komponent till en vertex av en annan komponent. Men detta är inte fallet i starkt sammankopplade komponenter. Två starkt anslutna komponenter blir inte en enda starkt ansluten komponent om det bara finns en enkelriktad kant från en SCC till en annan SCC.

java pseudokod

unidrawio-(2)

Brute Force Approach för att hitta starkt anslutna komponenter

Den enkla metoden är att för varje vertex i (som inte är en del av någon starkt komponent) hitta de hörn som kommer att vara den del av starkt sammankopplade komponent som innehåller vertex i. Två vertex i och j kommer att vara i samma starkt sammankopplade komponent om de finns en riktad väg från vertex i till vertex j och vice versa.

Låt oss förstå tillvägagångssättet med hjälp av följande exempel:

Börjar med vertex 1. Det finns väg från vertex 1 till vertex 2 och vice versa. På samma sätt finns en väg från vertex 1 till vertex 3 och vice versa. Så, vertex 2 och 3 kommer att vara i samma starkt anslutna komponent som vertex 1. Även om det finns en riktad bana från vertex 1 till vertex 4 och vertex 5. Men det finns ingen riktad bana från vertex 4,5 till vertex 1 så vertex 4 och 5 kommer inte att vara i samma starkt anslutna komponent som vertex 1. Således bildar vertex 1,2 och 3 en starkt ansluten komponent.
För Vertex 2 och 3 har starkt ansluten komponent redan fastställts.
För vertex 4 finns det en väg från vertex 4 till vertex 5 men det finns ingen väg från vertex 5 till vertex 4. Så vertex 4 och 5 kommer inte att vara i samma starkt anslutna komponent. Så både Vertex 4 och Vertex 5 kommer att vara en del av Single Strongly Connected Component.
Därför kommer det att finnas 3 starkt anslutna komponenter {1,2,3}, {4} och {5}.

Nedan är implementeringen av ovanstående tillvägagångssätt:

C++

 #include  using namespace std; class GFG { public:  // dfs Function to reach destination  bool dfs(int curr, int des, vector>& adj, vektor & vis) { // Om curr node är destination 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;  } } } returnerar falskt;  } // För att berätta om det finns sökväg från källan till // destination bool isPath(int src, int des, vektor>& adj) { vektor vis(adj.size() + 1, 0);  return dfs(src, des, adj, vis);  } // Funktion för att returnera alla starkt anslutna //-komponenter i en graf.  vektor> findSCC(int n, vektor>& a) { // Lagrar alla starkt anslutna komponenter.  vektor> ans;  // Lagrar om en vertex är en del av någon starkt // ansluten komponentvektor är_scc(n + 1, 0);  vektor> adj(n + 1);  för (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);  för (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.findSCC(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, Lista vis) { // Om curr node är destination 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;  } } } returnerar falskt;  } // För att berätta om det finns sökväg från källan till // destination boolean isPath(int src, int des, List> adj) { Lista vis = new ArrayList(adj.size() + 1);  för (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, List> a) { // Lagrar alla starkt anslutna komponenter.  Lista> ans = new ArrayList();  // Lagrar om en vertex är en del av någon Starkt // Connected Component List is_scc = ny ArrayList(n + 1);  för (int i = 0; i<= n; i++) {  is_scc.add(0);  }  List> adj = new ArrayList();  för (int i = 0; i<= n; i++) {  adj.add(new ArrayList());  }  for (List edge : a) { adj.get(edge.get(0)).add(edge.get(1));  } // Att korsa alla hörn för (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);  för (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(new ArrayList(List.of(1, 3)));  edges.add(new ArrayList(List.of(1, 4)));  edges.add(new ArrayList(List.of(2, 1)));  edges.add(new ArrayList(List.of(3, 2)));  edges.add(new ArrayList(List.of(4, 5)));  Lista> ans = obj.findSCC(V, kanter);  System.out.println('Stärkt anslutna komponenter är:');  för (lista x : ans) { for (int y : x) { System.out.print(y + ' ');  } System.out.println();  } } } // Denna kod är bidragit av shivamgupta310570>

Pytonorm

 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, Lista vis) { // Om curr node är destinationen, 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;  } } } returnerar falskt;  } // För att berätta om det finns en sökväg från källa till destination public bool IsPath(int src, int des, List> adj) { var show = ny lista (adj.Räkna + 1);  för (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, List> a) { // Lagrar alla starkt anslutna komponenter var ans = new List>();  // Lagrar om en vertex är en del av någon starkt ansluten komponent var isScc = new List (n + 1);  för (int i = 0; i< n + 1; i++)  {  isScc.Add(0);  }  var adj = new List>(n + 1);  för (int i = 0; i< n + 1; i++)  {  adj.Add(new List ());  } för (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);  för (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 lista> { ny lista { 1, 3 }, ny lista { 1, 4 }, ny lista { 2, 1 }, ny lista { 3, 2 }, ny lista { 4, 5 } };  Lista> ans = obj.FindSCC(V, kanter);  Console.WriteLine('Stärkt anslutna komponenter är:');  foreach (var x in ans) { foreach (var y in x) { Console.Write(y + ' ');  } Console.WriteLine();  } } } // Denna kod är bidragit 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(() =>[]);  för (låt 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>

Produktion

Strongly Connected Components are: 1 2 3 4 5>

Tidskomplexitet: O(n * (n + m)), eftersom vi för varje hörnpar kontrollerar om det finns en väg mellan dem.
Hjälputrymme: O(N)

strängar till heltal

Effektivt tillvägagångssätt för att hitta starkt anslutna komponenter (SCC)

För att hitta SCC i en graf kan vi använda algoritmer som Kosarajus algoritm eller Tarjans algoritm . Låt oss utforska dessa algoritmer steg för steg.

1. Kosarajus algoritm :

Kosarajus algoritm innefattar två huvudfaser:

Utföra Depth-First Search (DFS) på originalgrafen :
- Vi gör först en DFS på den ursprungliga grafen och registrerar sluttiderna för noderna (dvs tiden då DFS avslutar utforska en nod helt).
Utför DFS på den transponerade grafen :
- Vi vänder sedan om riktningen för alla kanter i grafen för att skapa den transponerade grafen.
- Därefter utför vi en DFS på den transponerade grafen, med hänsyn till noder i fallande ordning efter deras sluttider som registrerats i den första fasen.
- Varje DFS-övergång i denna fas kommer att ge oss en SCC.

Här är en förenklad version av Kosarajus algoritm:

DFS på originalgraf : Spela in sluttider.
Transponera grafen : Vänd alla kanter.
DFS på transponerad graf : Bearbeta noder i ordning efter minskande sluttider för att hitta SCC.

2. Tarjans algoritm :

Tarjans algoritm är mer effektiv eftersom den hittar SCC i ett enda DFS-pass med hjälp av en stack och lite extra bokföring:

DFS Traversal : Under DFS, upprätthåll ett index för varje nod och det minsta index (lågtänkvärde) som kan nås från noden.
Stack : Håll reda på noder för närvarande i rekursionsstacken (en del av den aktuella SCC som utforskas).
Identifiera SCC : När en nods låglänkvärde är lika med dess index betyder det att vi har hittat en SCC. Poppa alla noder från stacken tills vi når den aktuella noden.

Här är en förenklad översikt över Tarjans algoritm:

Initieraindex>till 0.
Utför DFS för varje obesökt nod.
- Ställ in nodens index och låglänkvärde.
- Skjut noden på stapeln.
- För varje intilliggande nod, utför antingen DFS om den inte har besökts eller uppdatera låglänksvärdet om det finns i stacken.
- Om nodens låglänkvärde är lika med dess index, poppar noder från stacken för att bilda en SCC.

Slutsats

Förstå och hitta starkt sammankopplade komponenter i en riktad graf är avgörande för många tillämpningar inom datavetenskap. Kosarajus och Tarjans Algoritmer är effektiva sätt att identifiera SCC, var och en med sin egen strategi och fördelar. Genom att behärska dessa koncept kan du bättre analysera och optimera strukturen och beteendet hos komplexa nätverk.