Bagaimana untuk melaksanakan algoritma traversal graf menggunakan java

Cara menggunakan Java untuk melaksanakan algoritma traversal graf

Graf ialah struktur data penting dalam matematik diskret dan sering digunakan untuk menerangkan hubungan antara perkara. Algoritma traversal graf merujuk kepada proses melawati semua nod dalam graf secara berurutan bermula dari nod tertentu dan mengikut peraturan tertentu. Algoritma traversal graf yang biasa digunakan termasuk carian mendalam-dahulu (DFS) dan carian luas-dahulu (BFS). Artikel ini akan memperkenalkan cara menggunakan bahasa Java untuk melaksanakan kedua-dua algoritma traversal graf ini dan menyediakan kod contoh khusus.

1. Carian pertama mendalam (DFS)

Carian pertama mendalam ialah algoritma traversal prapesanan yang melawati nod bersebelahan secara rekursif bermula dari nod permulaan sehingga ia tidak menemui nod bersebelahan yang belum dilawati, dan kemudian Backtrack ke nod sebelumnya dan terus melawati nod bersebelahan yang tidak dilawati sehingga keseluruhan graf dilalui.

Berikut ialah contoh kod untuk merentasi graf melalui carian mendalam-dahulu:

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);
    }
 
    void DFSUtil(int v, Boolean visited[]) {
        visited[v] = true;
        System.out.print(v + " ");
 
        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }
 
    void DFS(int v) {
        Boolean visited[] = new Boolean[V];
        Arrays.fill(visited, false);
 
        DFSUtil(v, visited);
    }
 
    public static void main(String args[]) {
        Graph g = new Graph(4);
 
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
 
        System.out.println("从顶点2开始的遍历结果：");
        g.DFS(2);
    }
}

Hasil keluaran:

从顶点2开始的遍历结果：
2 0 1 3

2. Carian pertama-luas (BFS)

Carian pertama-luas ialah algoritma lintasan mendatar nod permulaan, lawati nod lapisan demi lapisan dalam urutan sehingga keseluruhan graf dilalui. Gunakan baris gilir untuk melaksanakan carian pertama keluasan, mengambil satu nod daripada baris gilir pada satu masa, dan kemudian menambah nod bersebelahan yang tidak dilawati pada baris gilir.

Berikut ialah contoh kod untuk merentasi graf melalui carian luas pertama:

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);
    }
 
    void BFS(int v) {
        boolean visited[] = new boolean[V];
 
        LinkedList<Integer> queue = new LinkedList<Integer>();
 
        visited[v] = true;
        queue.add(v);
 
        while (queue.size() != 0) {
            v = queue.poll();
            System.out.print(v + " ");
 
            Iterator<Integer> i = adj[v].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
 
    public static void main(String args[]) {
        Graph g = new Graph(4);
 
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
 
        System.out.println("从顶点2开始的遍历结果：");
        g.BFS(2);
    }
}

Hasil keluaran:

从顶点2开始的遍历结果：
2 0 3 1

Dalam kod sampel di atas, kami menggunakan senarai bersebelahan untuk mewakili struktur graf dan membina graf dengan menambah tepi. Kemudian, kami memanggil kaedah DFS dan BFS masing-masing untuk melintasi graf. Hasil keluaran ialah urutan nod yang diperolehi oleh algoritma traversal.

Ringkasan:

Melalui pengenalan dan contoh kod artikel ini, kita boleh belajar cara menggunakan bahasa Java untuk melaksanakan algoritma traversal graf, termasuk carian mendalam-dahulu dan carian luas-dahulu. Kedua-dua algoritma traversal ini digunakan secara meluas dalam realiti, seperti perangkak web, penyelesaian maze dan medan lain. Menguasai algoritma traversal graf, kami boleh menyelesaikan masalah berkaitan dengan cepat dan berkesan.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma traversal graf menggunakan java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!