Рубрики

Java программа для топологической сортировки

Топологическая сортировка для направленного ациклического графа (DAG) представляет собой линейное упорядочение вершин, такое, что для каждого направленного ребра uv вершина u предшествует v в упорядочении. Топологическая сортировка для графа невозможна, если граф не является DAG.

Например, топологическая сортировка следующего графика — «5 4 2 3 1 0». Для графа может быть несколько топологических сортировок. Например, другая топологическая сортировка следующего графика — «4 5 2 3 1 0». Первая вершина в топологической сортировке — это всегда вершина с градусом 0 (вершина без входящих ребер).

Джава

// Java-программа для печати топологической сортировки DAG

import java.io.*;

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

  

    // Рекурсивная функция, используемая topologicalSort

    void topologicalSortUtil(int v, boolean visited[],

                             Stack stack)

    {

        // Пометить текущий узел как посещенный.

        visited[v] = true;

        Integer i;

  

        // Повторять для всех смежных вершин

        // вершина

        Iterator<Integer> it = adj[v].iterator();

        while (it.hasNext())

        {

            i = it.next();

            if (!visited[i])

                topologicalSortUtil(i, visited, stack);

        }

  

        // Вставляем текущую вершину в стек, в котором хранится результат

        stack.push(new Integer(v));

    }

  

    // Функция для топологической сортировки. Оно использует

    // рекурсивный topologicalSortUtil ()

    void topologicalSort()

    {

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

            System.out.print(stack.pop() + " ");

    }

  

    // Метод драйвера

    public static void main(String args[])

    {

        // Создать график, приведенный на диаграмме выше

        Graph g = new Graph(6);

        g.addEdge(5, 2);

        g.addEdge(5, 0);

        g.addEdge(4, 0);

        g.addEdge(4, 1);

        g.addEdge(2, 3);

        g.addEdge(3, 1);

  

        System.out.println("Following is a Topological " +

                           "sort of the given graph");

        g.topologicalSort();

    }

}
// Этот код предоставлен Aakash Hasija

Выход:

Following is a Topological Sort of the given graph
5 4 2 3 1 0

Пожалуйста, обратитесь к полной статье о топологической сортировке для более подробной информации!

Рекомендуемые посты:

Java программа для топологической сортировки

0.00 (0%) 0 votes