Cara menggunakan java untuk melaksanakan algoritma sambungan graf-javaTutorial-php.cn

Cara menggunakan java untuk melaksanakan algoritma sambungan graf

PHPz

Lepaskan： 2023-09-19 13:27:15

asal

789 orang telah melayarinya

Cara menggunakan java untuk melaksanakan algoritma sambungan graf

Cara menggunakan Java untuk melaksanakan algoritma ketersambungan graf

Pengenalan:
Graf ialah salah satu daripada struktur data biasa sains komputer , yang terdiri daripada nod (bucu) dan tepi. Ketersambungan graf bermakna semua nod dalam graf boleh disambungkan antara satu sama lain melalui tepi. Dalam bidang algoritma dan rangkaian, menilai ketersambungan graf adalah sangat penting kerana ia boleh membantu kami menyelesaikan banyak masalah, seperti penyelesaian masalah dalam rangkaian, analisis hubungan dalam rangkaian sosial, dsb. Artikel ini akan memperkenalkan cara menggunakan Java untuk melaksanakan algoritma sambungan graf dan memberikan contoh kod khusus.

Perwakilan graf
Di Jawa, kita boleh menggunakan matriks bersebelahan atau senarai bersebelahan graf untuk mewakili graf. Matriks bersebelahan ialah tatasusunan dua dimensi di mana elemen tatasusunan mewakili hubungan sambungan antara nod. Senarai bersebelahan ialah tatasusunan senarai terpaut, di mana setiap senarai terpaut mewakili nod jiran setiap nod.
Depth First Search (DFS) Algorithm
Depth First Search ialah algoritma untuk merentasi graf. Ia bermula dari nod permulaan dan melawati nod jirannya yang tidak dilawati secara rekursif sehingga tiada nod boleh dicapai. Melalui carian mendalam-pertama, kita boleh merentasi keseluruhan graf dan menentukan sama ada graf disambungkan.

Berikut ialah kod Java yang menggunakan algoritma carian kedalaman pertama untuk menentukan sama ada graf disambungkan:

import java.util.ArrayList;
import java.util.List;

public class GraphConnectivity {
    private int numNodes;
    private List<List<Integer>> adjList;
    private boolean[] visited;

    public GraphConnectivity(int numNodes) {
        this.numNodes = numNodes;
        adjList = new ArrayList<>();
        for (int i = 0; i < numNodes; i++) {
            adjList.add(new ArrayList<>());
        }
        visited = new boolean[numNodes];
    }

    public void addEdge(int src, int dest) {
        adjList.get(src).add(dest);
        adjList.get(dest).add(src);
    }

    private void dfs(int node) {
        visited[node] = true;
        for (int neighbor : adjList.get(node)) {
            if (!visited[neighbor]) {
                dfs(neighbor);
            }
        }
    }

    public boolean isGraphConnected() {
        dfs(0);

        for (boolean visit : visited) {
            if (!visit) {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        GraphConnectivity graph = new GraphConnectivity(5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(3, 4);
        
        System.out.println("Is the graph connected? " + graph.isGraphConnected());
    }
}

Salin selepas log masuk

Dalam kod di atas, kami mencipta kelas GraphConnectivity untuk mewakili graf. Gunakan senarai bersebelahan untuk menyimpan sambungan antara nod. Kaedah addEdge digunakan untuk menambah tepi antara nod. Kaedah dfs ialah kaedah rekursif yang digunakan untuk carian pertama mendalam. Kaedah isGraphConnected menyemak ketersambungan graf dengan memanggil dfs(0). GraphConnectivity类来表示一个图。使用邻接表来保存节点之间的连接关系。addEdge方法用于添加节点之间的边。dfs方法是一个递归方法，用于进行深度优先搜索。isGraphConnected方法通过调用dfs(0)来检查图的连通性。

运行以上代码，输出结果为：Is the graph connected? false。这表明图不是连通的，因为节点0、1、2是连通的，节点3、4是连通的，但节点0和节点3不是连通的。

广度优先搜索（BFS）算法
广度优先搜索也是一种用于遍历图的算法。它从一个起始节点开始，访问其邻居节点，并逐层遍历，直到找到目标节点或遍历完整个图。通过广度优先搜索，我们可以找到两个节点之间的最短路径，也可以判断图是否连通。

下面是使用广度优先搜索算法来判断一个图是否连通的Java代码：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class GraphConnectivity {
    private int numNodes;
    private List<List<Integer>> adjList;
    private boolean[] visited;

    public GraphConnectivity(int numNodes) {
        this.numNodes = numNodes;
        adjList = new ArrayList<>();
        for (int i = 0; i < numNodes; i++) {
            adjList.add(new ArrayList<>());
        }
        visited = new boolean[numNodes];
    }

    public void addEdge(int src, int dest) {
        adjList.get(src).add(dest);
        adjList.get(dest).add(src);
    }

    public boolean isGraphConnected() {
        Queue<Integer> queue = new LinkedList<>();
        int startNode = 0;
        queue.offer(startNode);
        visited[startNode] = true;

        while (!queue.isEmpty()) {
            int node = queue.poll();

            for (int neighbor : adjList.get(node)) {
                if (!visited[neighbor]) {
                    queue.offer(neighbor);
                    visited[neighbor] = true;
                }
            }
        }

        for (boolean visit : visited) {
            if (!visit) {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        GraphConnectivity graph = new GraphConnectivity(5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(3, 4);

        System.out.println("Is the graph connected? " + graph.isGraphConnected());
    }
}

Salin selepas log masuk

在上述代码中，我们调用Queue来实现广度优先搜索。我们通过queue.offer(startNode)

Jalankan kod di atas, hasil output ialah: Adakah graf disambungkan? Ini menunjukkan bahawa graf tidak bersambung, kerana nod 0, 1, 2 disambungkan, nod 3, 4 disambungkan, tetapi nod 0 dan nod 3 tidak disambungkan.

Breadth-first search juga merupakan algoritma untuk merentasi graf. Ia bermula dari nod permulaan, melawati nod jirannya dan merentasi lapisan demi lapisan sehingga ia menemui nod sasaran atau merentasi keseluruhan graf. Melalui carian luas-pertama, kita boleh mencari laluan terpendek antara dua nod dan menentukan sama ada graf disambungkan.

Queue

queue.offer(startNode)

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