Algoritma DFS dalam Java

Algoritma DFS ialah algoritma traversal yang ditakrifkan sebagai algoritma carian yang disingkatkan sebagai carian depth-first, yang dikenali sebagai algoritma graf juga kerana ia mencari dalam struktur pokok yang kelihatan seperti struktur graf dan oleh itu ia bermula dari akar dan merentasi bersama graf di bawah dengan cabang yang berbeza. Secara umum, algoritma DFS dalam Java ditakrifkan sebagai algoritma traversal yang melintasi dalam struktur pokok atau graf yang bermula dari nod akar pada titik awal dan pergi dalam dengan setiap cawangan sehingga ia mencapai nod terakhir mana-mana cawangan terakhir carian sedemikian diketahui. sebagai carian mendalam-pertama dan ini menyediakan 3 cara berbeza DFS seperti carian prapesanan, tertib dan lintasan pasca pesanan.

Mulakan Kursus Pembangunan Perisian Percuma Anda

Pembangunan web, bahasa pengaturcaraan, ujian perisian & lain-lain

Algoritma:

DFS ialah algoritma seragam yang menghasilkan penyelesaian tidak optimum dan algoritma DFS berfungsi seperti berikut:

Langkah 1: Mulakan dengan nod punca mana-mana graf atau pokok tertentu.

Langkah 2: Sekarang pertimbangkan nod akar sebagai nod pertama graf dan letakkan nod ini di bahagian atas tindanan atau senarai.

Langkah 3: Sekarang cari nod bersebelahan nod akar, yang merupakan nod pertama, dan tambahkan nod bersebelahan ini pada senarai senarai nod bersebelahan yang lain.

Langkah 4: Kemudian teruskan menambah nod bersebelahan setiap nod dalam tindanan atau senarai selepas nod akar.

Langkah 5: Teruskan langkah3 hingga 4 sehingga anda mencapai nod hujung cawangan terakhir dalam graf atau senarai nod bersebelahan menjadi kosong.

Oleh itu, algoritma DFS dalam Java ialah salah satu algoritma carian traversal yang mencari secara mendalam sehingga nod akhir dari nod awal. Walau bagaimanapun, kadangkala ia mengelirukan apabila anda melintasi graf, sama ada melalui cawangan kiri atau kanan; untuk menyelesaikan masalah ini, terdapat 3 jenis DFS prapesanan, pesanan dan pasca pesanan untuk melintasi pokok mengikut susunan yang ditentukan.

Bagaimanakah algoritma DFS berfungsi dengan Contoh?

Di Java, algoritma DFS berfungsi mengikut algoritma yang diterangkan di atas. Algoritma DFS untuk graf tidak terarah akan bermula dari nod akar dengan meletakkan nod akar ini terlebih dahulu dalam satu timbunan yang boleh dianggap sebagai timbunan yang dilawati yang memegang nod yang dilawati, dan kemudian meletakkan semua nod bersebelahan nod akar dalam ini timbunan yang dilawati di mana nod akar hadir. Kemudian merentasi graf dan kemudian cari nod bersebelahan setiap nod bersebelahan akar dan teruskan sehingga nod terakhir graf dan melintasi nod ini dengan meletakkan semua nod dalam timbunan lain jadi selepas menyelesaikan carian, timbunan yang dilawati dipaparkan yang memberikan nod yang telah dilalui melalui graf.

Contoh #1

Sekarang mari kita lihat contoh algoritma DFS mudah yang dilaksanakan dalam bahasa pengaturcaraan Java pada graf terputus.

Kod:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class vertex
{
int root, dest;
public vertex(int root, int dest)
{
this.root = root;
this.dest = dest;
}
}
class graphstruc
{
List<List<Integer>> adjList = null;
graphstruc(List<vertex> v, int N)
{
adjList = new ArrayList<>();
for (int i = 0; i < N; i++) {
adjList.add(new ArrayList<>());
}
for (vertex e: v)
{
int src = e.root;
int dest = e.dest;
adjList.get(src).add(dest);
adjList.get(dest).add(src);
}
}
}
class Main
{
public static void DFS(graphstruc graph, int v, boolean[] d)
{
d[v] = true;
System.out.print(v + " ");
for (int u: graph.adjList.get(v))
{
if (!d[u]) {
DFS(graph, u, d);
}
}
}
public static void main(String[] args)
{
List<vertex> v = Arrays.asList(
new vertex(1, 2), new vertex(1, 7), new vertex(1, 8),
new vertex(2, 3), new vertex(2, 6), new vertex(3, 4),
new vertex(3, 5), new vertex(8, 9), new vertex(8, 12),
new vertex(9, 10), new vertex(9, 11), new vertex(10, 12),
new vertex(10, 13), new vertex(11, 14)
);
final int N = 15;
graphstruc g = new graphstruc(v, N);
boolean[] d = new boolean[N];
System.out.println("Demonstration of Depth First Search algorithm in Java is as follows:");
for (int i = 0; i < N; i++)
{
if (!d[i]) {
DFS(g, i, d);
}
}
}
}

Output:

Dalam contoh di atas, kita mula-mula mentakrifkan bucu kelas di mana kita akan mengisytiharkan punca dan bucu destinasi dalam graf di mana bucu kelas ini menyimpan bucu graf. Kemudian kami mentakrifkan graphstruc kelas untuk mengisytiharkan bucu bersebelahan nod akar dan menambah nod bersebelahan ini dalam senarai. Kami menyimpan bucu bersebelahan dan kemudian menambah bucu bersebelahan bucu ini dalam senarai. Kemudian untuk melaksanakan DFS, kami mengisytiharkan kelas DFS yang melaluinya kami akan mengenal pasti nod semasa daripada graf yang diberikan, dan kami terus mengenal pasti nod bersebelahan setiap nod dan menambah nod senarai bersebelahan. Kemudian akhir sekali, dalam kelas utama, kami akan mentakrifkan senarai bucu graf sebagai tatasusunan bersama-sama dengan jumlah bilangan nod, dan selepas memanggil fungsi DFS, ia akan memaparkan senarai dalam senarai carian DFS seperti yang ditunjukkan dalam tangkapan skrin di atas , yang merupakan output.

Contoh #2

Sekarang mari kita lihat pelaksanaan DFS dengan pelbagai jenis pesanan traversal seperti prapesanan, inorder dan traversal pasca pesanan di Jawa. Di bawah, kita akan melihat pelaksanaan prapesanan dalam Java.

Kod:

class vertex
{
int data;
vertex l, r;
public vertex(int k)
{
data = k;
l = r = null;
}
}
class Main
{
public static void preorder(vertex root)
{
if (root == null) {
return;
}
System.out.print(root.data + " ");
preorder(root.l);
preorder(root.r);
}
public static void main(String[] args)
{
vertex root = new vertex(2);
root.l = new vertex(3);
root.r = new vertex(1);
root.l.l = new vertex(6);
root.r.l = new vertex(4);
root.r.r = new vertex(5);
root.r.l.l = new vertex(8);
root.r.l.r = new vertex(7);
preorder(root);
}
}

Output:

Dalam contoh di atas juga serupa dengan contoh sebelumnya di mana di sini satu-satunya perbezaan ialah kita mentakrifkan perintah lintasan dalam algoritma DFS. Dalam hal ini, kami hanya mentakrifkan tertib traversal prapesanan, yang, apabila ditakrifkan, ia akan melintasi graf kedalaman-pertama dalam susunan sebagai nod akar, nod kiri dan nod kanan. Oleh itu di sini, kami telah mengisytiharkan nod 2 sebagai nod akar dan nod 3 sebagai nod kiri dan nod 6 sebagai nod kanan, dan seterusnya. Output adalah seperti yang ditunjukkan dalam tangkapan skrin di atas.

Kesimpulan

Artikel ini menyimpulkan bahawa algoritma DFS dalam Java ialah algoritma traversal untuk mencari atau mencari graf secara mendalam sehingga nod terakhir dilawati. Kerumitan masa untuk algoritma DFS biasanya diwakili dalam O(E+V), di mana E untuk tepi dan V untuk bucu graf. Terdapat banyak aplikasi algoritma DFS yang berbeza berdasarkan susunan traversalnya yang diklasifikasikan sebagai traversal DFS inorder, preorder dan postorder melalui graf.

Atas ialah kandungan terperinci Algoritma DFS dalam Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!