Ən kiçik topoloji sıralama (Həll təhlili)

$a = (a_{1}, a_{2}, ..., a_{n})$ a = (a_1, a_2, ..., a_n) ardıcıllığı $b = (b_{1}, b_{2}, ..., b_{n})$ b = (b_1, b_2, ..., b_n) ardıcıllığından leksikoqrafik olaraq kiçikdir, əgər onların fərqləndiyi ilk $i$ mövqeyində $a_{i} < b_{i}$ a_i < b_i şərti ödənilirsə. Beləliklə, leksikoqrafik olaraq ən kiçik topoloji sıralamanı əldə etmək üçün birinci yerə ən kiçik mümkün təpəni, ikinci yerə isə artıq seçilmiş birinci təpə şərtilə ən kiçik mümkün təpəni qoymaq lazımdır və bu qayda ilə davam edilir.

Məsələni həll etmək üçün Kan alqoritmindən (Kahn) istifadə edək. Hər bir təpə üçün onun daxil olan dərəcəsini — ona daxil olan qövslərin sayını — hesablayaq. Bir təpə topoloji sıralamada növbəti yerdə yalnız o halda dura bilər ki, onun bütün sələfləri artıq yazılmış olsun, yəni onun cari daxil olan dərəcəsi sıfıra bərabər olsun.

Klassik Kan alqoritmində daxil olan dərəcəsi sıfır olan təpələr adi növbədə saxlanılır və ixtiyari qaydada çıxarılır. Leksikoqrafik olaraq ən kiçik cavabı əldə etmək üçün növbəni prioritet növbə (və ya set çoxluğu) ilə əvəz edək, buradan hər dəfə ən kiçik nömrəli təpə çıxarılır.

Alqoritm aşağıdakı kimidir:

bütün təpələrin daxil olan dərəcələrini hesablayırıq;
daxil olan dərəcəsi sıfır olan bütün təpələri prioritet növbəyə yerləşdiririk — məhz onlar topoloji sıralamaya başlaya bilər;
növbə boş olmayana qədər, ondan ən kiçik nömrəli $v$ təpəsini çıxarıb cavaba əlavə edirik. Sonra hər bir $v \to u$ v \to u qövsü üçün $u$ təpəsinin daxil olan dərəcəsini $1$ azaldırıq. Əgər o sıfıra bərabər olarsa, $u$ -nu növbəyə əlavə edirik.

Dövrün aşkarlanması. Əgər qraf dövr (sikl) ehtiva edirsə, dövrdəki heç bir təpə heç vaxt sıfır daxil olan dərəcə əldə etməyəcək və növbəyə düşməyəcək. Buna görə də, əgər alqoritmin işi başa çatdıqdan sonra cavaba $n$ -dən az təpə daxil olmuşdursa, topoloji sıralama mümkün deyil — $- 1$ çıxarırıq.

Mürəkkəblik. Hər bir təpə prioritet növbəyə dəqiq bir dəfə əlavə edilir və oradan çıxarılır, hər bir qövs bir dəfə nəzərdən keçirilir. İşləmə vaxtı $O (n l o g n + m)$ O(n~log~n + m) təşkil edir.

Nümunə

Nümunədə verilən qraf aşağıdakı görünüşə malikdir:

Bu qraf bir neçə topoloji sıralama variantına imkan verir. Məsələn:

$1, 4, 6, 3, 2, 5$ 1, 4, 6, 3, 2, 5;
$4, 3, 6, 1, 2, 5$ 4, 3, 6, 1, 2, 5;
$3, 1, 4, 2, 6, 5$ 3, 1, 4, 2, 6, 5;

Leksikoqrafik olaraq ən kiçik topoloji sıralama budur

1, 3, 4, 2, 6, 5

1, 3, 4, 2, 6, 5

Leksikoqrafik olaraq ən böyük topoloji sıralama isə budur

4, 6, 3, 1, 2, 5

4, 6, 3, 1, 2, 5

Alqoritmin reallaşdırılması — set

Giriş qrafını qonşuluq siyahısı $g$ şəklində saxlayırıq. Təpələrin daxil olan dərəcələrini $I n D e g r ee$ InDegree massivində saxlayırıq. Qrafın topoloji sıralanmış təpələrini $O r d er$ massivinə yerləşdiririk.

vector<vector<int> > g;
vector<int> InDegree, Order;
set<int> minHeap;

Giriş qrafını oxuyuruq.

scanf("%d %d", &n, &m);
g.resize(n + 1);
InDegree.resize(n + 1);

Bütün təpələr üçün daxil olan dərəcələri hesablayırıq. Hər bir $(a, b)$ qövsü üçün $b$ təpəsinin daxil olan dərəcəsinin qiymətini artırırıq.

for (i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
  InDegree[b]++;
}

Daxil olan dərəcəsi sıfır olan bütün təpələri $min H e a p$ çoxluğuna əlavə edirik.

for (i = 1; i < InDegree.size(); i++)
  if (InDegree[i] == 0) minHeap.insert(i);

$min H e a p$ çoxluğu boş olana qədər topoloji sıralama alqoritminin işini davam etdiririk.

while (!minHeap.empty())
{

$min H e a p$ -dan ən kiçik nömrəli $v$ təpəsini çıxarırıq və onu topoloji sıranın sonuna əlavə edirik.

  v = *minHeap.begin();
  minHeap.erase(minHeap.begin());
  Order.push_back(v);

$v$ təpəsindən çıxan bütün $(v, t o)$ (v, to) qövslərini qrafdan silirik. Hər bir belə qövs üçün $t o$ təpəsinin daxil olan dərəcəsini azaldırıq. Əgər $t o$ təpəsinin daxil olan dərəcəsi sıfır olarsa, onu çoxluğa əlavə edirik, buradan o topoloji sıra siyahısına düşəcək.

 for (int to : g[v])
 {
   InDegree[to]--;
   if (InDegree[to] == 0) minHeap.insert(to);
 }
}

Əgər alqoritmin işi başa çatdıqdan sonra $O r d er$ massivinə $n$ təpənin hamısı əlavə edilməyibsə, deməli qraf dövr ehtiva edir və topoloji sıralama mümkün deyil.

if (Order.size() < n)
  printf("-1");
else

Qrafın təpələrini leksikoqrafik olaraq ən kiçik topoloji sırada çıxarırıq.

  for (i = 0; i < Order.size(); i++)
    printf("%d ", Order[i]);
printf("\n");

Alqoritmin reallaşdırılması — priority queue

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

vector<vector<int> > g;
vector<int> InDegree, Order;
priority_queue<long long, vector<long long>, greater<long long> > pq;
int i, n, m, a, b, v, to;

int main(void)
{
  scanf("%d %d", &n, &m);
  g.resize(n + 1);
  InDegree.resize(n + 1);

  for (i = 0; i < m; i++)
  {
    scanf("%d %d", &a, &b);
    g[a].push_back(b);
    InDegree[b]++;
  }

  for (i = 1; i < InDegree.size(); i++)
    if (InDegree[i] == 0) pq.push(i);

  while (!pq.empty())
  {
    v = pq.top(); pq.pop();
    Order.push_back(v);

    for (int to : g[v])
    {
      InDegree[to]--;
      if (InDegree[to] == 0) pq.push(to);
    }
  }

  if (Order.size() < n)
    printf("-1");
  else
    for (int x : Order)
      printf("%d ", x);
  printf("\n");
  return 0;
}

Java

Java reallaşdırılması — priority queue

import java.util.*;
import java.io.*;

public class Main
{
  static ArrayList<ArrayList<Integer>> g;
  static ArrayList<Integer> top;
  static int InDegree[];
  static int n, m, flag = 0;
  
  public static void main(String[] args)
  {
    FastScanner con = new FastScanner(System.in);
    n = con.nextInt();
    m = con.nextInt();
    g = new ArrayList<ArrayList<Integer>>();
    InDegree = new int[n+1];
      
    for (int i = 0; i <= n; i++)
      g.add(new ArrayList<Integer>());

    for (int i = 0; i < m; i++)
    {
      int a = con.nextInt();
      int b = con.nextInt();     
      g.get(a).add(b);
      InDegree[b]++;
    }

    PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    for(int i = 1; i <= n; i++)
      if (InDegree[i] == 0) pq.add(i);

    top = new ArrayList<Integer>();
    while (!pq.isEmpty())
    {
      int v = pq.poll();
      top.add(v);
      for (int to : g.get(v))
      {
        InDegree[to]--;
        if (InDegree[to] == 0) pq.add(to);
      }
    }

    if (top.size() < n)
      System.out.println("-1");
    else
    {
      for (int x : top) System.out.print(x + " ");
        System.out.println();
    }
  }
}	

class FastScanner
{
  BufferedReader br;
  StringTokenizer st;
 
  public FastScanner(InputStream inputStream)
  {
    br = new BufferedReader(new InputStreamReader(inputStream));
    st = new StringTokenizer("");
  }
 
  public String next()
  {
    while (!st.hasMoreTokens())
    {
      try
      {
        st = new StringTokenizer(br.readLine());
      } catch (Exception e)
      {
        return null;
      }
    }
    return st.nextToken();
  }
 
  public int nextInt()
  {
    return Integer.parseInt(next());
  }
}

Java

Python reallaşdırılması — priority queue

$h e a pq$ modulundan $h e a pp u s h$ heappush və $h e a pp o p$ funksiyalarını idxal edirik. $h e a pq$ — Python-un qurğuşun (daxili) kitabxanasıdır, bu da yığın (heap) əsasında prioritet növbənin reallaşdırılmasını təqdim edir.

from heapq import heappush, heappop

Qrafdakı təpələrin sayı $n$ və qövslərin sayı $m$ -i oxuyuruq.

n, m = map(int, input().split())

Giriş qrafını qonşuluq siyahısı $g$ şəklində saxlayırıq. Təpələrin daxil olan dərəcələrini $I n D e g r ee$ InDegree massivində saxlayırıq.

g = [[] for _ in range(n + 1)]
InDegree = [0] * (n + 1)

Giriş qrafını oxuyuruq. Bütün təpələr üçün daxil olan dərəcələri hesablayırıq. Hər bir $(a, b)$ qövsü üçün $b$ təpəsinin daxil olan dərəcəsinin qiymətini artırırıq.

for _ in range(m):
  a, b = map(int, input().split())
  g[a].append(b)
  InDegree[b] += 1

Daxil olan dərəcəsi sıfır olan bütün təpələri $min H e a p$ siyahısına əlavə edirik.

minHeap = []
for i in range(1, len(InDegree)):
  if InDegree[i] == 0:
    heappush(minHeap, i)

Qrafın topoloji sıralanmış təpələrini $O r d er$ massivinə yerləşdiririk.

Order = []

$min H e a p$ siyahısı boş olana qədər topoloji sıralama alqoritminin işini davam etdiririk.

while minHeap:

$min H e a p$ -dan ən kiçik nömrəli $v$ təpəsini çıxarırıq və onu topoloji sıranın sonuna əlavə edirik.

  v = heappop(minHeap)
  Order.append(v)

$v$ təpəsindən çıxan bütün $(v, t o)$ (v, to) qövslərini qrafdan silirik. Hər bir belə qövs üçün $t o$ təpəsinin daxil olan dərəcəsini azaldırıq. Əgər $t o$ təpəsinin daxil olan dərəcəsi sıfır olarsa, onu növbəyə əlavə edirik, buradan o topoloji sıra siyahısına düşəcək.

  for to in g[v]:
    InDegree[to] -= 1
    if InDegree[to] == 0:
      heappush(minHeap, to)

Əgər alqoritmin işi başa çatdıqdan sonra $O r d er$ massivinə $n$ təpənin hamısı əlavə edilməyibsə, deməli qraf dövr ehtiva edir və topoloji sıralama mümkün deyil.

if len(Order) < n:
  print(-1)

Qrafın təpələrini leksikoqrafik olaraq ən kiçik topoloji sırada çıxarırıq.

else:
  print(*Order)