logo

TechCodeview

Components fortament connectats

Components fortament connectats (SCC) són un concepte fonamental en la teoria de grafs i els algorismes. En un gràfic dirigit, a Component fortament connectat és un subconjunt de vèrtexs on cada vèrtex del subconjunt és accessible des de qualsevol altre vèrtex del mateix subconjunt travessant les arestes dirigides. Trobar el SCC d'un gràfic pot proporcionar informació important sobre l'estructura i la connectivitat del gràfic, amb aplicacions en diversos camps com ara anàlisi de xarxes socials, rastreig web i encaminament de la xarxa . Aquest tutorial explorarà la definició, les propietats i els algorismes eficients per identificar components fortament connectats en estructures de dades de gràfics.

substituint la cadena a java

Taula de contingut



Què són els components fortament connectats (SCC)?

A component fortament connectat d'un graf dirigit és un subgraf màxim on cada parell de vèrtexs és mútuament accessible. Això vol dir que per a dos nodes A i B qualsevol d'aquest subgraf, hi ha un camí d'A a B i un camí de B a A.

Per exemple: El gràfic següent té dues components fortament connectades {1,2,3,4} i {5,6,7} ja que hi ha un camí des de cada vèrtex a tots els altres vèrtexs en el mateix component fortament connectat.

scc_fianldrawio

Component fortament connectat



Per què són importants els components fortament connectats (SCC)?

Entendre els SCC és crucial per a diverses aplicacions com ara:

  • Anàlisi de xarxes : Identificació de clústers de nodes estretament interconnectats.
  • Optimització dels rastrejadors web : determinació de parts del gràfic web que estan estretament vinculades.
  • Resolució de dependències : En programari, entendre quins mòduls són interdependents.

Diferència entre components connectats i fortament connectats ( SCC)

Connectivitat en a gràfic no dirigit fa referència a si dos vèrtexs són accessibles entre si o no. Es diu que dos vèrtexs estan connectats si hi ha un camí entre ells. Mentrestant Fortament connectat és aplicable només a gràfics dirigits . Un subgraf d'un gràfic dirigit es considera un Components fortament connectats (SCC) si i només si per a cada parell de vèrtexs A i B , existeix un camí des de A a B i un camí des de B a A . Vegem per què el mètode dfs estàndard per trobar components connectats en un gràfic no es pot utilitzar per determinar components fortament connectats.

Considereu el gràfic següent:



scc_fianldrawio

Ara, comencem a dfs crida des del vèrtex 1 per visitar altres vèrtexs.

dfs_finaldrawio

Per què no es pot utilitzar el mètode DFS convencional per trobar els components fortament connectats?

Es pot arribar a tots els vèrtexs des del vèrtex 1. Però els vèrtexs 1 i 5,6,7 no poden estar en el mateix component fortament connectat perquè no hi ha un camí dirigit des del vèrtex 5,6 o 7 fins al vèrtex 1. El gràfic té dos components connectats {1,2,3,4} i {5,6,7}. Per tant, el mètode dfs convencional no es pot utilitzar per trobar els components fortament connectats.

substituïu la cadena a java

Connectant dos components fortament connectats per una vora unidireccional

Dos components connectats diferents es converteixen en un únic component si s'afegeix una aresta entre un vèrtex d'un component a un vèrtex d'un altre component. Però aquest no és el cas dels components fortament connectats. Dos components fortament connectats no es converteixen en un únic component fortament connectat si només hi ha una vora unidireccional d'un SCC a un altre SCC.

models d'aprenentatge automàtic

unidrawio-(2)

Enfocament de força bruta per trobar components fortament connectats

El mètode senzill serà per a cada vèrtex i (que no forma part de cap component fortament) trobar els vèrtexs que seran la part del component fortament connectat que conté el vèrtex i. Dos vèrtex i i j estaran en el mateix component fortament connectat si hi ha un camí dirigit des del vèrtex i al vèrtex j i viceversa.

Entenem l'enfocament amb l'ajuda de l'exemple següent:

dibuix d'exemple

  • Començant pel vèrtex 1. Hi ha un camí des del vèrtex 1 al vèrtex 2 i viceversa. De la mateixa manera, hi ha un camí des del vèrtex 1 al vèrtex 3 i viceversa. Així doncs, els vèrtexs 2 i 3 estaran al mateix component fortament connectat que el vèrtex 1. Encara que hi ha un camí dirigit del vèrtex 1 al vèrtex 4 i al vèrtex 5. Però no hi ha cap camí dirigit des del vèrtex 4,5 fins al vèrtex 1, per tant el vèrtex 4 i 5 no estarà en el mateix component fortament connectat que el vèrtex 1. Així, els vèrtexs 1,2 i 3 formen un component fortament connectat.
  • Per al vèrtex 2 i 3, ja s'ha determinat el component fortament connectat.
  • Per al vèrtex 4, hi ha un camí del vèrtex 4 al vèrtex 5, però no hi ha cap camí del vèrtex 5 al vèrtex 4. Per tant, el vèrtex 4 i 5 no estaran al mateix component fortament connectat. Així, tant Vertex 4 com Vertex 5 formaran part d'un component únic fortament connectat.
  • Per tant, hi haurà 3 components fortament connectats {1,2,3}, {4} i {5}.

A continuació es mostra la implementació de l'enfocament anterior:

C++ 
#include  using namespace std; class GFG { public:  // dfs Function to reach destination  bool dfs(int curr, int des, vector>& adj, vector & vis) { // Si el node curr és la destinació return true if (curr == des) { return true;  } vis[curr] = 1;  for (auto x : adj[curr]) { if (!vis[x]) { if (dfs(x, des, adj, vis)) { retorna cert;  } } } retorna fals;  } // Per saber si hi ha un camí des de l'origen fins a // la destinació bool isPath(int src, int des, vector>& adj) { vector vis(adj.size() + 1, 0);  retornar dfs(src, des, adj, vis);  } // Funció per retornar tot el // component fortament connectat d'un gràfic.  vector> findSCC(int n, vector>& a) { // Emmagatzema tots els components fortament connectats.  vector> ans;  // Emmagatzema si un vèrtex forma part d'un vector de components forts // connectats is_scc(n + 1, 0);  vector> adj(n + 1);  per (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);  per (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> vores{ { 1, 3 }, { 1, 4 }, { 2, 1 }, { 3, 2 }, { 4, 5 } };  vector> ans = obj.findSCC(V, vores);  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, Llista vis) { // Si el node curr és la destinació 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)) { retorna cert;  } } } retorna fals;  } // Per saber si hi ha un camí des de l'origen fins a // la destinació booleà isPath(int src, int des, List> adj) { Llista vis = new ArrayList(adj.size() + 1);  per (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, Llista> a) { // Emmagatzema tots els components fortament connectats.  Llista> ans = new ArrayList();  // Emmagatzema si un vèrtex forma part de qualsevol // Llista de components fortament connectats is_scc = new ArrayList (n + 1);  per (int i = 0; i<= n; i++) {  is_scc.add(0);  }  List> adj = new ArrayList();  per (int i = 0; i<= n; i++) {  adj.add(new ArrayList());  }  for (List edge : a) { adj.get(edge.get(0)).add(edge.get(1));  } // Travessant tots els vèrtexs per a (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);  per (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> vores = new ArrayList();  edges.add(new ArrayList(Llista.de(1, 3)));  edges.add(new ArrayList(Llista.de(1, 4)));  edges.add(new ArrayList(Llista.de(2, 1)));  edges.add(new ArrayList(Llista.de(3, 2)));  edges.add(new ArrayList(Lista.de(4, 5)));  Llista> ans = obj.findSCC(V, vores);  System.out.println('Els components fortament connectats són:');  per (Llista x : ans) { for (int y : x) { System.out.print(y + ' ');  } System.out.println();  } } } // Aquest codi és aportat per shivamgupta310570>>>Python
C# 
using System; using System.Collections.Generic; class GFG {  // dfs Function to reach destination  public bool Dfs(int curr, int des, List> adj, Llista vis) { // Si el node curr és la destinació, retorna true if (curr == des) { retorna true;  } vis[curr] = 1;  foreach (var x in adj[curr]) { if (vis[x] == 0) { if (Dfs(x, des, adj, vis)) { retorna cert;  } } } retorna fals;  } // Per saber si hi ha un camí des de l'origen fins a la destinació public bool IsPath(int src, int des, List> adj) { var show = llista nova (adj.Compte + 1);  per (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, Llista> a) { // Emmagatzema tots els components fortament connectats var ans = new List>();  // Emmagatzema si un vèrtex forma part de qualsevol component fortament connectat var isScc = new List (n + 1);  per (int i = 0; i< n + 1; i++)  {  isScc.Add(0);  }  var adj = new List>(n + 1);  per (int i = 0; i< n + 1; i++)  {  adj.Add(new List ());  } per (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.Afegir(i);  per (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> vores = nova llista> { nova llista {1, 3}, llista nova {1, 4}, llista nova {2, 1}, llista nova { 3, 2 }, llista nova { 4, 5 } };  Llista> ans = obj.FindSCC(V, vores);  Console.WriteLine('Els components fortament connectats són:');  foreach (var x in ans) { foreach (var y en x) { Consola.Write(y + ' ');  } Console.WriteLine();  } } } // Aquest codi és aportat per shivamgupta310570>>>Javascript
Sortida 
Strongly Connected Components are: 1 2 3 4 5>

Complexitat temporal: O(n * (n + m)), perquè per a cada parell de vèrtexs estem comprovant si hi ha un camí entre ells.
Espai auxiliar: O(N)

diferència entre amor i gust

Enfocament eficient per trobar components fortament connectats (SCC)

Per trobar els SCC en un gràfic, podem utilitzar algorismes com Algoritme de Kosaraju o Algoritme de Tarjan . Explorem aquests algorismes pas a pas.

1. Algoritme de Kosaraju :

L'algoritme de Kosaraju inclou dues fases principals:

  1. Realització de la cerca en profunditat (DFS) al gràfic original :
    • Primer fem un DFS al gràfic original i registrem els temps d'acabament dels nodes (és a dir, el moment en què el DFS acaba d'explorar un node completament).
  2. Realització de DFS al gràfic transposat :
    • A continuació, invertim la direcció de totes les arestes del gràfic per crear el gràfic transposat.
    • A continuació, realitzem un DFS sobre el gràfic transposat, considerant els nodes en ordre decreixent dels seus temps d'acabament registrats a la primera fase.
    • Cada travessia DFS en aquesta fase ens donarà un SCC.

Aquí teniu una versió simplificada de l'algoritme de Kosaraju:

  1. DFS al gràfic original : Registre els temps de finalització.
  2. Transposa el gràfic : Inverteix totes les vores.
  3. DFS sobre gràfic transposat : Processa els nodes per ordre decreixent dels temps de finalització per trobar els SCC.

2. Algoritme de Tarjan :

L'algoritme de Tarjan és més eficient perquè troba SCC en una sola passada DFS mitjançant una pila i una comptabilitat addicional:

  1. Travessia DFS : Durant el DFS, mantingueu un índex per a cada node i l'índex més petit (valor d'enllaç baix) al qual es pot arribar des del node.
  2. Pila : Feu un seguiment dels nodes que es troben actualment a la pila de recursivitat (part de l'SCC actual que s'està explorant).
  3. Identificació de SCC : Quan el valor d'enllaç baix d'un node és igual al seu índex, vol dir que hem trobat un SCC. Extraieu tots els nodes de la pila fins que arribem al node actual.

Aquí hi ha un esquema simplificat de l'algoritme de Tarjan:

  1. Inicialitzarindex>a 0.
  2. Per a cada node no visitat, feu DFS.
    • Estableix l'índex del node i el valor d'enllaç baix.
    • Empenyeu el node a la pila.
    • Per a cada node adjacent, feu DFS si no es visita o actualitzeu el valor d'enllaç baix si es troba a la pila.
    • Si el valor d'enllaç baix del node és igual al seu índex, desplegueu els nodes de la pila per formar un SCC.

Conclusió

Entendre i trobar components fortament connectats en un gràfic dirigit és essencial per a moltes aplicacions en informàtica. de Kosaraju i de Tarjan Els algorismes són maneres eficients d'identificar SCC, cadascun amb el seu propi enfocament i avantatges. Dominant aquests conceptes, podeu analitzar i optimitzar millor l'estructura i el comportament de xarxes complexes.