Rumah >Java >javaTutorial >Cara menggunakan java untuk melaksanakan algoritma titik potong graf
Cara menggunakan java untuk melaksanakan algoritma titik potong graf memerlukan contoh kod khusus
Graf adalah salah satu konsep penting dalam diskret matematik, melalui perwakilan Graf boleh menerangkan hubungan dan perkaitan yang muncul dalam pelbagai masalah dunia sebenar. Dalam algoritma berkaitan graf, mencari titik potong graf adalah masalah yang mencabar. Titik potong graf juga dipanggil titik sambungan atau bahagian atas potong Ia bermaksud bahawa dalam graf bersambung tidak berarah, jika bucu dan semua tepi yang berkaitan dengan bucu dibuang, graf asal tidak lagi bersambung dipanggil titik potong.
Artikel ini akan memperkenalkan cara menggunakan bahasa pengaturcaraan Java untuk melaksanakan algoritma titik potong graf dan memberikan contoh kod khusus. Pertama, kita perlu mentakrifkan struktur data graf Berikut ialah contoh kelas graf ringkas:
import java.util.*; class Graph { private int V; // 顶点的数量 private LinkedList<Integer> adj[]; // 邻接表形式的图 // 构造函数,初始化图 Graph(int v) { V = v; adj = new LinkedList[v]; for (int i=0; i<v; ++i) adj[i] = new LinkedList(); } // 添加边到图中 void addEdge(int v, int w) { adj[v].add(w); adj[w].add(v); } // 递归函数,实现割点算法 void cutVertexUtil(int u, boolean visited[], int disc[], int low[], int parent[], boolean ap[]) { int children = 0; visited[u] = true; disc[u] = low[u] = ++time; Iterator<Integer> i = adj[u].iterator(); while (i.hasNext()) { int v = i.next(); if (!visited[v]) { children++; parent[v] = u; cutVertexUtil(v, visited, disc, low, parent, ap); low[u] = Math.min(low[u], low[v]); if (parent[u] == -1 && children > 1) ap[u] = true; if (parent[u] != -1 && low[v] >= disc[u]) ap[u] = true; } else if (v != parent[u]) low[u] = Math.min(low[u], disc[v]); } } // 割点算法的主函数 void cutVertices() { boolean visited[] = new boolean[V]; int disc[] = new int[V]; int low[] = new int[V]; int parent[] = new int[V]; boolean ap[] = new boolean[V]; // 记录割点 for (int i = 0; i < V; i++) { parent[i] = -1; visited[i] = false; ap[i] = false; } for (int i = 0; i < V; i++) if (visited[i] == false) cutVertexUtil(i, visited, disc, low, parent, ap); System.out.println("割点:"); for (int i = 0; i < V; i++) if (ap[i] == true) System.out.print(i+" "); System.out.println(); } public static void main(String args[]) { Graph g1 = new Graph(5); g1.addEdge(1, 0); g1.addEdge(0, 2); g1.addEdge(2, 1); g1.addEdge(0, 3); g1.addEdge(3, 4); System.out.println("以下是图g1中的割点:"); g1.cutVertices(); Graph g2 = new Graph(4); g2.addEdge(0, 1); g2.addEdge(1, 2); g2.addEdge(2, 3); System.out.println("以下是图g2中的割点:"); g2.cutVertices(); Graph g3 = new Graph(7); g3.addEdge(0, 1); g3.addEdge(1, 2); g3.addEdge(2, 0); g3.addEdge(1, 3); g3.addEdge(1, 4); g3.addEdge(1, 6); g3.addEdge(3, 5); g3.addEdge(4, 5); System.out.println("以下是图g3中的割点:"); g3.cutVertices(); } }
Dalam contoh kod ini, kami mencipta kelas Graf untuk mewakili graf, menggunakan bentuk satu senarai bersebelahan untuk menyimpan tepi graf. Dalam pelaksanaan algoritma titik potong, kami menggunakan kaedah traversal carian mendalam-pertama dan menggunakan beberapa tatasusunan tambahan untuk merekodkan status akses, masa penemuan, nod nenek moyang yang paling awal dilawati dan menandakan titik potong. Dengan memanggil fungsi cutVertices()
, anda boleh mencari titik potong dalam graf dan mengeluarkan indeks titik potong. cutVertices()
函数,可以找到图中的割点,并输出割点的索引。
代码示例中的main
Atas ialah kandungan terperinci Cara menggunakan java untuk melaksanakan algoritma titik potong graf. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!