Рубрики

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

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

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

// Программа на C ++ для печати топологической сортировки DAG
#include <iostream>
#include <list>
#include <stack>

using namespace std;

  
// Класс для представления графика

class Graph {

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

  

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

    list<int>* adj;

  

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

    void topologicalSortUtil(int v, bool visited[], stack<int>& Stack);

  

public:

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

  

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

    void addEdge(int v, int w);

  

    // выводит топологическую сортировку полного графа

    void topologicalSort();

};

  

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<int>[V];

}

  

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

{

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

}

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

void Graph::topologicalSortUtil(int v, bool visited[],

                                stack<int>& Stack)

{

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

    visited[v] = true;

  

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

    list<int>::iterator i;

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

        if (!visited[*i])

            topologicalSortUtil(*i, visited, Stack);

  

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

    Stack.push(v);

}

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

void Graph::topologicalSort()

{

    stack<int> Stack;

  

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

    bool* visited = new bool[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) {

        cout << Stack.top() << " ";

        Stack.pop();

    }

}

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

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 << "Following is a Topological Sort of the given graph n";

    g.topologicalSort();

  

    return 0;

}

Выход:

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

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

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

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

0.00 (0%) 0 votes