Bagaimana untuk melaksanakan algoritma pengisihan topologi menggunakan java

Cara menggunakan Java untuk melaksanakan algoritma pengisihan topologi

Isihan topologi ialah algoritma yang biasa digunakan dalam teori graf, digunakan untuk memberikan asiklik terarah. bucu graf (Graf Asiklik Berarah, singkatan DAG) diisih. Pengisihan topologi boleh digunakan untuk menyelesaikan masalah seperti kebergantungan atau penjadualan tugas. Dalam artikel ini, kami akan memperkenalkan cara menggunakan Java untuk melaksanakan algoritma pengisihan topologi dan memberikan contoh kod yang sepadan.

Idea pelaksanaan penyisihan topologi adalah seperti berikut:

1. Pertama, kita perlu mentakrifkan struktur data graf terarah, yang boleh diwakili oleh senarai bersebelahan. Senarai bersebelahan ialah struktur data yang menyimpan graf Setiap bucu sepadan dengan senarai terpaut, dan senarai terpaut menyimpan semua bucu bersebelahan dengan bucu.

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);
    }
}

2. Kemudian, kita perlu melaksanakan kaedah pengisihan topologi. Proses pelaksanaan pengisihan topologi boleh dibahagikan kepada dua langkah:

   a, hitung darjah dalam setiap bucu (iaitu, berapa banyak bucu menghala kepadanya), dan mulakan a. baris gilir untuk menyimpan dalam darjah Puncak ialah 0.

   b Keluarkan bucu dari baris gilir secara berterusan dan kurangkan dalam darjah bucu bersebelahannya Jika dalam darjah bucu menjadi 0, tambahkannya pada baris gilir.

   c. Ulangi langkah (b) sehingga baris gilir kosong dan dalam darjah semua bucu menjadi 0. Jika bilangan bucu yang dimasukkan pada masa ini tidak sama dengan bilangan bucu graf, ini bermakna terdapat kitaran dalam graf dan pengisihan topologi tidak dapat diselesaikan.

import java.util.*;

class TopologicalSort {
    // 拓扑排序算法
    void topologicalSort(Graph graph) {
        int V = graph.V;
        LinkedList<Integer> adj[] = graph.adj;

        int[] indegree = new int[V];
        for (int i = 0; i < V; ++i) {
            for (int j : adj[i]) {
                indegree[j]++;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < V; ++i) {
            if (indegree[i] == 0) {
                queue.add(i);
            }
        }

        int count = 0;
        ArrayList<Integer> result = new ArrayList<>();

        while (!queue.isEmpty()) {
            int u = queue.poll();
            result.add(u);

            for (int v : adj[u]) {
                if (--indegree[v] == 0) {
                    queue.add(v);
                }
            }
            count++;
        }

        if (count != V) {
            System.out.println("图中存在环，无法进行拓扑排序");
            return;
        }

        System.out.println("拓扑排序结果：");
        for (int i : result) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

3. Akhir sekali, kita boleh mencipta graf dan memanggil kaedah isihan topologi untuk mengisihnya.

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

        TopologicalSort topologicalSort = new TopologicalSort();
        topologicalSort.topologicalSort(graph);
    }
}

Di atas ialah langkah dan contoh kod untuk melaksanakan algoritma pengisihan topologi menggunakan Java. Melalui algoritma pengisihan topologi, kami boleh menyelesaikan masalah seperti kebergantungan atau penjadualan tugas dengan berkesan.

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