Heim> Java> javaLernprogramm> Hauptteil

Lernen mit disjunkten Mengengraphen

PHPz
Freigeben: 2024-08-15 20:31:48
Original
722 Leute haben es durchsucht

Disjoint Set Graph Learning

Disjunkte Menge ist eine Datenstruktur, die im Kruskal Minimal Spanning Tree verwendet wird.
Diese Datenstrukturen ermöglichen es uns, die Vereinigung von zwei oder mehr Knoten zu erstellen.
Damit können wir feststellen, ob zwei Knoten zur gleichen Komponente des Diagramms gehören.
Die Zeitkomplexität ist O(4alpha) (wenn wir die Pfadkomprimierung verwenden, die wir verwenden, sonst ist sie logarithmisch), was eine konstante Zeitkomplexität ist, die nachgewiesen wurde.

Weitere Informationen finden Sie unter

class Main{ int parent[] = new int[100000]; int rank[] = new int[100000]; void makeSet(){ for(int i=1;i<=n;i++){ parent[i] = i; // initially parent of node i is i itself rank[i] =0;// intially rank of all the nodes are 0 } } int findParent(int node){ if(node == parent[node]) return node; // ie if the parent of 'node' is 'node' itself then just return the node. //return findParent(parent[node]);// else recursively call findParent to get the parent of this union. // in order to path conpress (making sure that every node is connected to its parent in the given union) return parent[node] = findParent(parent[node]); //example : 7->6->4->3 , here 3 is the parent of this union, so in order to get the parent of 7 which is 3 we can path compress it. like 7->3,6->3,4->3 etc. } void union(int u, int v){ u = findParent(u); v = findParent(v); if(rank[u] < rank[v]) parent[u] =v; else if (rank[u] > rank[v]) parent[v] = u; else parent[u] =v; // or parent[v] = u; // here u and v had the same rank //and now v became parent of u hence its rank will increase rank[v]++; } public static void main(String args[]) throws Exception{ Main m = new Main(); //if we where given no of nodes as n BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); while(n>0){ int u = n--; int v = n--; m.union(u,v);// this will create union of n nodes } // if 2 and 3 belong to the same component or not find out if(findParent(2)! = findParent(3)) System.out.println("Different component"); else System.out.println("Same component"); } }
Nach dem Login kopieren

Das obige ist der detaillierte Inhalt vonLernen mit disjunkten Mengengraphen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Quelle:dev.to
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage
Über uns Haftungsausschluss Sitemap
Chinesische PHP-Website:Online-PHP-Schulung für das Gemeinwohl,Helfen Sie PHP-Lernenden, sich schnell weiterzuentwickeln!