Рубрики

Все топологические виды ориентированного ациклического графа

Топологическая сортировка для D irected Циклический G Раф (ДАГ) представляет собой линейное упорядочение вершин таким образом, что для каждого направленного ребра уф, вершина и предшествует V в заказе. Топологическая сортировка для графа невозможна, если граф не является DAG.

Учитывая DAG, выведите все топологические виды графика.

For example, consider the below graph.

All topological sorts of the given graph are: 4 5 0 2 3 1 4 5 2 0 3 1 4 5 2 3 0 1 4 5 2 3 1 0 5 2 3 4 0 1 5 2 3 4 1 0 5 2 4 0 3 1 5 2 4 3 0 1 5 2 4 3 1 0 5 4 0 2 3 1 5 4 2 0 3 1 5 4 2 3 0 1 5 4 2 3 1 0

В Направленном ациклическом графе много раз мы можем иметь вершины, которые не связаны друг с другом, из-за чего мы можем упорядочить их разными способами. Эти различные топологические сортировки важны во многих случаях, например, если между вершинами также имеется некоторый относительный вес, который должен минимизировать, тогда мы должны позаботиться об относительном упорядочении, а также об их относительном весе, что создает необходимость проверки через все возможные топологические упорядочения.
Мы можем пройти через все возможные упорядочения путем обратного отслеживания, шаг алгоритма заключается в следующем:

  1. Инициализируйте все вершины как не посещенные.
  2. Теперь выберите вершину, которая не посещается и имеет нулевую степень, и уменьшите степень всех этих вершин на 1 (что соответствует удалению ребер). Теперь добавьте эту вершину в результат и снова вызовите рекурсивную функцию и вернитесь назад.
  3. После возврата из функции сбрасываются значения посещенных, результат и степень для перечисления других возможностей.

Ниже приведена реализация вышеуказанных шагов.

C ++

// C ++ программа для печати всех топологических сортов графа
#include <bits/stdc++.h>

using namespace std;

  

class Graph

{

    int V;    // Количество вершин

  

    // Указатель на массив, содержащий список смежности

    list<int> *adj;

  

    // Вектор для хранения степени вершин

    vector<int> indegree;

  

    // Функция, используемая alltopologicalSort

    void alltopologicalSortUtil(vector<int>& res,

                                bool visited[]);

  

public:

    Graph(int V);   // Конструктор

  

    // функция для добавления ребра на график

    void addEdge(int v, int w);

  

    // Печатает все топологические сортировки

    void alltopologicalSort();

};

  
// Конструктор графа

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<int>[V];

  

    // Инициализируем все степени с 0

    for (int i = 0; i < V; i++)

        indegree.push_back(0);

}

  
// Сервисная функция для добавления ребра

void Graph::addEdge(int v, int w)

{

    adj[v].push_back(w); // Добавить w в список v.

  

    // увеличиваем внутреннюю степень w на 1

    indegree[w]++;

}

  
// Основная рекурсивная функция для печати всего возможного
// топологические сортировки

void Graph::alltopologicalSortUtil(vector<int>& res,

                                   bool visited[])

{

    // Чтобы указать, найдены ли все топологические

    // или не

    bool flag = false

  

    for (int i = 0; i < V; i++)

    {

        // Если не указано 0 и еще не посещено

        // выбираем только эту вершину

        if (indegree[i] == 0 && !visited[i])

        {

            // уменьшение степени смежных вершин

            list<int>:: iterator j;

            for (j = adj[i].begin(); j != adj[i].end(); j++)

                indegree[*j]--;

  

            // в том числе в результате

            res.push_back(i);

            visited[i] = true;

            alltopologicalSortUtil(res, visited);

  

            // Сброс посещенных, Res и Indegree для

            // возвращение

            visited[i] = false;

            res.erase(res.end() - 1);

            for (j = adj[i].begin(); j != adj[i].end(); j++)

                indegree[*j]++;

  

            flag = true;

        }

    }

  

    // Мы достигаем здесь, если все вершины посещены.

    // Таким образом, мы печатаем решение здесь

    if (!flag)

    {

        for (int i = 0; i < res.size(); i++)

            cout << res[i] << " ";

        cout << endl;

    }

}

  
// Функция выполняет всю топологическую сортировку.
// Используется рекурсивный alltopologicalSortUtil ()

void Graph::alltopologicalSort()

{

    // Пометить все вершины как не посещенные

    bool *visited = new bool[V];

    for (int i = 0; i < V; i++)

        visited[i] = false;

  

    vector<int> res;

    alltopologicalSortUtil(res, visited);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

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

    Graph g(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);

  

    cout << "All Topological sorts\n";

  

    g.alltopologicalSort();

  

    return 0;

}

Джава

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

import java.util.*;

  

class Graph {

    int V; // Количество вершин

  

    List<Integer> adjListArray[];

  

    public Graph(int V) {

  

        this.V = V;

  

        @SuppressWarnings("unchecked")

        List<Integer> adjListArray[] = new LinkedList[V];

  

        this.adjListArray = adjListArray;

  

        for (int i = 0; i < V; i++) {

            adjListArray[i] = new LinkedList<>();

        }

    }

    // Сервисная функция для добавления ребра

    public void addEdge(int src, int dest) {

  

        this.adjListArray[src].add(dest);

  

    }

      

    // Основная рекурсивная функция для печати всего возможного

    // топологические сортировки

    private void allTopologicalSortsUtil(boolean[] visited, 

                        int[] indegree, ArrayList<Integer> stack) {

        // Чтобы указать, найдены ли все топологические

        // или не

        boolean flag = false;

  

        for (int i = 0; i < this.V; i++) {

            // Если не указано 0 и еще не посещено

            // выбираем только эту вершину

            if (!visited[i] && indegree[i] == 0) {

                  

                // в том числе в результате

                visited[i] = true;

                stack.add(i);

                for (int adjacent : this.adjListArray[i]) {

                    indegree[adjacent]--;

                }

                allTopologicalSortsUtil(visited, indegree, stack);

                  

                // Сброс посещенных, Res и Indegree для

                // возвращение

                visited[i] = false;

                stack.remove(stack.size() - 1);

                for (int adjacent : this.adjListArray[i]) {

                    indegree[adjacent]++;

                }

  

                flag = true;

            }

        }

        // Мы достигаем здесь, если все вершины посещены.

        // Таким образом, мы печатаем решение здесь

        if (!flag) {

            stack.forEach(i -> System.out.print(i + " "));

            System.out.println();

        }

  

    }

      

    // Функция выполняет всю топологическую сортировку.

    // Используется рекурсивный alltopologicalSortUtil ()

    public void allTopologicalSorts() {

        // Пометить все вершины как не посещенные

        boolean[] visited = new boolean[this.V];

  

        int[] indegree = new int[this.V];

  

        for (int i = 0; i < this.V; i++) {

  

            for (int var : this.adjListArray[i]) {

                indegree[var]++;

            }

        }

  

        ArrayList<Integer> stack = new ArrayList<>();

  

        allTopologicalSortsUtil(visited, indegree, stack);

    }

      

    // Код драйвера

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

  

        System.out.println("All Topological sorts");

        graph.allTopologicalSorts();

    }

}

Выход :

All Topological sorts
4 5 0 2 3 1 
4 5 2 0 3 1 
4 5 2 3 0 1 
4 5 2 3 1 0 
5 2 3 4 0 1 
5 2 3 4 1 0 
5 2 4 0 3 1 
5 2 4 3 0 1 
5 2 4 3 1 0 
5 4 0 2 3 1 
5 4 2 0 3 1 
5 4 2 3 0 1 
5 4 2 3 1 0 

Эта статья предоставлена Уткаршем Триведи. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

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

Все топологические виды ориентированного ациклического графа

0.00 (0%) 0 votes