Рубрики

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

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

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

Решение на основе DFS для поиска топологической сортировки уже обсуждалось.

В этой статье мы увидим другой способ найти линейное упорядочение вершин в ориентированном ациклическом графе (DAG). Подход основан на следующем факте:

DAG G имеет по крайней мере одну вершину с внутренней степенью 0 и одну вершину с внешней степенью 0 .
Доказательство: Там простое доказательство вышеуказанного факта , что DAG не содержит цикл , что означает , что все пути будут конечной длины. Теперь позвольте S быть самым длинным путем от u (источник) до v (пункт назначения). Поскольку S — самый длинный путь, не может быть никакого входящего фронта к u и никакого исходящего фронта от v, если бы это произошло, то S не был бы самым длинным путем.
=> indegree (u) = 0 и outdegree (v) = 0

Алгоритм:
Этапы поиска топологического порядка DAG:

Шаг 1: Вычислить в градусах (количество входящих ребер) для каждой вершины, представленной в DAG, и инициализировать количество посещенных узлов как 0.

Шаг 2: Выберите все вершины со степенью 0 и добавьте их в очередь (операция постановки в очередь)

Шаг 3: Удалить вершину из очереди (операция удаления из очереди), а затем.

  1. Увеличение количества посещенных узлов на 1.
  2. Уменьшение степени на 1 для всех соседних узлов.
  3. Если степень соседних узлов уменьшается до нуля, добавьте его в очередь.

Шаг 5: повторяйте шаг 3, пока очередь не станет пустой.

Шаг 5: Если количество посещенных узлов не равно количеству узлов в графе, то топологическая сортировка для данного графа невозможна.

Как узнать степень каждого узла?
Есть 2 способа вычисления степени каждой вершины:
Возьмите массив в градусах, который будет отслеживать
1) Обойдите массив ребер и просто увеличьте счетчик целевого узла на 1.

for each node in Nodes
    indegree[node] = 0;
for each edge(src,dest) in Edges
    indegree[dest]++

Сложность времени: O (V + E)

2) Просмотрите список для каждого узла и затем увеличьте степень всех узлов, подключенных к нему, на 1.

    for each node in Nodes
        If (list[node].size()!=0) then
        for each dest in list
            indegree[dest]++;

Сложность времени: внешний цикл for будет выполняться V количество раз, а внутренний цикл for будет выполняться E количество раз, таким образом, общая сложность времени равна O (V + E).

Общая временная сложность алгоритма составляет O (V + E)

Ниже приведена реализация вышеуказанного алгоритма на C ++. Реализация использует метод 2, описанный выше, для нахождения степеней.

C ++

// Программа на C ++ для печати топологической сортировки графа
// используя Indegrees.
#include<bits/stdc++.h>

using namespace std;

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

class Graph

{

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

  

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

    list<int> *adj;

  

public:

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

  

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

    void addEdge(int u, int v);

  

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

    void topologicalSort();

};

  

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<int>[V];

}

  

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

{

    adj[u].push_back(v);

}

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

void Graph::topologicalSort()

{

    // Создать вектор для хранения всех степеней

    // вершины. Инициализировать все степени как 0.

    vector<int> in_degree(V, 0);

  

    // Обход списков смежности для заполнения степеней

    // вершины. Этот шаг занимает O (V + E) время

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

    {

        list<int>::iterator itr;

        for (itr = adj[u].begin(); itr != adj[u].end(); itr++)

             in_degree[*itr]++;

    }

  

    // Создаем очередь и ставим все вершины в очередь

    // градус 0

    queue<int> q;

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

        if (in_degree[i] == 0)

            q.push(i);

  

    // Инициализируем количество посещенных вершин

    int cnt = 0;

  

    // Создать вектор для сохранения результата (Топологический

    // упорядочение вершин)

    vector <int> top_order;

  

    // одна за другой удаляем вершины из очереди и очереди

    // смежно, если степень смежности становится 0

    while (!q.empty())

    {

        // Извлечение фронта очереди (или выполнение очереди)

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

        int u = q.front();

        q.pop();

        top_order.push_back(u);

  

        // Перебирать все соседние узлы

        // извлеченного из узла u и уменьшения их степени

        // на 1

        list<int>::iterator itr;

        for (itr = adj[u].begin(); itr != adj[u].end(); itr++)

  

            // Если в степени становится ноль, добавить его в очередь

            if (--in_degree[*itr] == 0)

                q.push(*itr);

  

        cnt++;

    }

  

    // Проверяем, был ли цикл

    if (cnt != V)

    {

        cout << "There exists a cycle in the graph\n";

        return;

    }

  

    // Распечатать топологический порядок

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

        cout << top_order[i] << " ";

    cout << endl;

}

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

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\n";

    g.topologicalSort();

  

    return 0;

}

Джава

// Java-программа для печати топологической сортировки графа
// используя Indegrees

import java.util.*;

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

class Graph

{

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

      

    // Массив List, который содержит

    // ссылки на список смежности

    // каждая вершина

    List <Integer> adj[];

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

    {

        this.V = V;

        adj = new ArrayList[V];

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

            adj[i]=new ArrayList<Integer>();

    }

      

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

    public void addEdge(int u,int v)

    {

        adj[u].add(v);

    }

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

    public void topologicalSort()

    {

        // Создать массив для хранения всех степеней

        // вершины. Инициализировать все степени как 0.

        int indegree[] = new int[V];

          

        // Обход списков смежности для заполнения степеней

        // вершины. Этот шаг занимает O (V + E) время

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

        {

            ArrayList<Integer> temp = (ArrayList<Integer>) adj[i];

            for(int node : temp)

            {

                indegree[node]++;

            }

        }

          

        // Создаем очередь и ставим все вершины в очередь

        // градус 0

        Queue<Integer> q = new LinkedList<Integer>();

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

        {

            if(indegree[i]==0)

                q.add(i);

        }

          

        // Инициализируем количество посещенных вершин

        int cnt = 0;

          

        // Создать вектор для сохранения результата (Топологический

        // упорядочение вершин)

        Vector <Integer> topOrder=new Vector<Integer>();

        while(!q.isEmpty())

        {

            // Извлечение фронта очереди (или выполнение очереди)

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

            int u=q.poll();

            topOrder.add(u);

              

            // Перебирать все соседние узлы

            // извлеченного из узла u и уменьшения их степени

            // на 1

            for(int node : adj[u])

            {

                // Если в степени становится ноль, добавить его в очередь

                if(--indegree[node] == 0)

                    q.add(node);

            }

            cnt++;

        }

          

        // Проверяем, был ли цикл

        if(cnt != V)

        {

            System.out.println("There exists a cycle in the graph");

            return ;

        }

          

        // Распечатать топологический порядок

        for(int i : topOrder)

        {

            System.out.print(i+" ");

        }

    }

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

class Main

{

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

        g.topologicalSort();

  

    }

}

питон

# Программа Python для печати топологической сортировки графа
# используя Indegrees

from collections import defaultdict

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

class Graph:

    def __init__(self,vertices):

        self.graph = defaultdict(list) #dictionary, содержащий список смежности

        self.V = vertices #No. вершин

  

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

    def addEdge(self,u,v):

        self.graph[u].append(v)

  

  

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

    def topologicalSort(self):

          

        # Создать вектор для хранения всех степеней

        # вершины. Инициализировать все степени как 0.

        in_degree = [0]*(self.V)

          

        # Перейдите списки смежности, чтобы заполнить степени

           # вершины. Этот шаг занимает O (V + E) время

        for i in self.graph:

            for j in self.graph[i]:

                in_degree[j] += 1

  

        # Создайте очередь и поставьте все вершины в очередь

        # Indegree 0

        queue = []

        for i in range(self.V):

            if in_degree[i] == 0:

                queue.append(i)

  

        # Инициализировать количество посещенных вершин

        cnt = 0

  

        # Создать вектор для сохранения результата (топологический

        # упорядочение вершин)

        top_order = []

  

        # Одна за другой удаляет вершины из очереди и очереди

        # примыкает, если степень смежности становится 0

        while queue:

  

            # Извлечь начало очереди (или выполнить очередь)

            # и добавить его в топологический порядок

            u = queue.pop(0)

            top_order.append(u)

  

            # Итерация по всем соседним узлам

            количество удаленных узлов u и уменьшение их степени

            # на 1

            for i in self.graph[u]:

                in_degree[i] -= 1

                # Если в степени становится ноль, добавить его в очередь

                if in_degree[i] == 0:

                    queue.append(i)

  

            cnt += 1

  

        # Проверьте, был ли цикл

        if cnt != self.V:

            print "There exists a cycle in the graph"

        else :

            # Печать топологического порядка

            print top_order

  

  

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

  

print "Following is a Topological Sort of the given graph"

g.topologicalSort()

  
# Этот код предоставлен Neelam Yadav

Выход :

Following is a Topological Sort
4 5 2 0 3 1

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

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

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

0.00 (0%) 0 votes