Bagaimana untuk melaksanakan algoritma pengisihan topologi graf menggunakan java

Cara menggunakan Java untuk melaksanakan algoritma pengisihan topologi graf

Pengenalan:
Graf ialah struktur data yang sangat biasa. Bidang sains komputer mempunyai pelbagai aplikasi. Algoritma pengisihan topologi ialah algoritma klasik dalam teori graf yang boleh mengisih graf akiklik terarah (DAG) untuk menentukan kebergantungan antara nod dalam graf. Artikel ini akan memperkenalkan cara menggunakan bahasa pengaturcaraan Java untuk melaksanakan algoritma pengisihan topologi graf, dengan contoh kod Java tertentu.

1 Tentukan struktur data graf
Sebelum melaksanakan algoritma pengisihan topologi, kita perlu mentakrifkan struktur data graf terlebih dahulu. Untuk memudahkan masalah, kita boleh menggunakan senarai bersebelahan untuk mewakili graf.

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

    // 其他图操作方法...
}

Dalam kod di atas, kami mentakrifkan kelas Graf, yang mengandungi integer V yang mewakili bilangan bucu dalam graf dan senarai bersebelahan adj[ ] , digunakan untuk menyimpan bucu bersebelahan setiap bucu. Graph类，它包含了一个整数V表示图中的顶点数，以及一个邻接表adj[]，用来存储各个顶点的邻接顶点。

二、实现拓扑排序算法
拓扑排序算法的基本思想是通过不断删除图中入度为0的顶点，直到图中所有顶点都被删除。下面是使用Java实现拓扑排序算法的代码示例：

class TopologicalSorting {
    private Graph graph;
    private int V;
    private LinkedList<Integer> resultList;

    TopologicalSorting(Graph g) {
        graph = g;
        V = g.V;
        resultList = new LinkedList<>();
    }

    void topologicalSortUtil(int v, boolean visited[], Stack<Integer> stack) {
        visited[v] = true;

        Iterator<Integer> it = graph.adj[v].iterator();
        while (it.hasNext()) {
            int i = it.next();
            if (!visited[i])
                topologicalSortUtil(i, visited, stack);
        }

        stack.push(v);
    }

    void topologicalSort() {
        Stack<Integer> stack = new Stack<>();
        boolean visited[] = new boolean[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;

        for (int i = 0; i < V; i++)
            if (visited[i] == false)
                topologicalSortUtil(i, visited, stack);

        while (stack.empty() == false)
            resultList.add(stack.pop());
    }

    // 输出结果
    void printResult() {
        System.out.println("拓扑排序结果：");
        for (int i : resultList)
            System.out.print(i + " ");
        System.out.println();
    }
}

在上述代码中，TopologicalSorting类是用来进行拓扑排序的类。其中，topologicalSortUtil方法是一个递归方法，用来实现具体的排序逻辑。topologicalSort方法是拓扑排序的入口方法，它利用递归方法对所有顶点进行逐个排序。最后的printResult方法用来输出排序结果。

三、示例
以下是一个使用拓扑排序算法的示例：

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

        TopologicalSorting ts = new TopologicalSorting(graph);
        ts.topologicalSort();
        ts.printResult();
    }
}

代码中创建了一个有向图，并添加了一些边。然后通过TopologicalSorting

2. Laksanakan algoritma pengisihan topologi

Idea asas algoritma pengisihan topologi adalah untuk memadamkan bucu secara berterusan dengan darjah 0 dalam graf sehingga semua bucu dalam graf dipadamkan. Berikut ialah contoh kod yang menggunakan Java untuk melaksanakan algoritma pengisihan topologi:
rrreee

Dalam kod di atas, kelas TopologicalSorting digunakan untuk pengisihan topologi. Antaranya, kaedah topologicalSortUtil ialah kaedah rekursif yang digunakan untuk melaksanakan logik pengisihan tertentu. Kaedah topologicalSort ialah kaedah kemasukan pengisihan topologi Ia menggunakan kaedah rekursif untuk mengisih semua bucu satu demi satu. Kaedah printResult terakhir digunakan untuk mengeluarkan hasil yang diisih. #🎜🎜##🎜🎜#3 Contoh#🎜🎜#Berikut ialah contoh menggunakan algoritma pengisihan topologi: #🎜🎜#rrreee#🎜🎜#Kod mencipta graf terarah dan menambah beberapa tepi. Kemudian lakukan pengisihan topologi dan keluarkan hasil melalui kelas TopologicalSorting. #🎜🎜##🎜🎜#Kesimpulan: #🎜🎜#Artikel ini memperkenalkan cara menggunakan bahasa Java untuk melaksanakan algoritma pengisihan topologi graf dan memberikan contoh kod khusus. Algoritma pengisihan topologi ialah algoritma klasik untuk menyelesaikan masalah pengisihan kebergantungan puncak dalam graf, dan ia sangat penting dalam aplikasi praktikal. Melalui pengenalan artikel ini, saya berharap dapat membantu pembaca memahami dan menguasai algoritma ini. #🎜🎜#

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