Topoloji sıralama (Həll təhlili)

İstiqamətlənmiş qrafın topoloji sıralaması onun təpələrinin elə nömrələnməsinə deyilir ki, hər bir u \to v tili üçün $u$ təpəsi ardıcıllıqda $v$ təpəsindən əvvəl yerləşsin. Topoloji sıralama yalnız və yalnız o halda mövcuddur ki, qrafda istiqamətlənmiş dövrlər olmasın (qraf asiklik olsun).

Məsələni dərinliyə axtarış vasitəsilə həll edək. Hər bir təpəyə bir rəng uyğun qoyaq:

• ağ — təpəyə hələ baş çəkilməyib;

• boz — təpəyə baş çəkilib, lakin onun emalı başa çatmayıb (təpə cari rekursiya stekində yerləşir);

• qara — təpə və ondan çatıla bilən bütün təpələr tam emal olunub.

Başlanğıcda bütün təpələr ağdır. Dərinliyə axtarışı hər bir ağ təpədən başladırıq. Təpəyə daxil olarkən onu boz rəngə, çıxarkən isə qara rəngə boyayırıq və həmin anda onu siyahıya əlavə edirik. Topoloji sıralamada təpələrin ardıcıllığı onların qara rəngə keçmə ardıcıllığının tərsi ilə üst-üstə düşür: tam emal olunan ilk təpə sıralamada sonuncu, sonuncu emal olunan təpə isə birinci olacaq.

Dövrün aşkarlanması. Əgər dolaşma zamanı boz təpəyə aparan tilə rast gəlinərsə, qrafda dövr var və topoloji sıralama mümkün deyil — $-1$ çap edirik.

Mürəkkəblik. Hər bir təpə və hər bir til bir dəfə emal olunur, buna görə də alqoritmin işləmə müddəti O(n + m) təşkil edir.

Nümunə

Nümunədə verilən qraf aşağıdakı kimidir:

Hər bir zirvənin yanında $v$, d[v] / f[v] işarələrini yerləşdirək, burada $d[v]$ — zirvənin emalının başlanma vaxtıdır, və $f[v]$ — onun emalının bitmə vaxtı. Topoloji sıralamada zirvələr $f[v]$ dəyərlərinin azalmasına görə yerləşdirilir.

Alqoritmin reallaşdırılması

Qrafdakı zirvələrin sayı çox olduğuna görə qrafı əlaqə siyahısı $g$ kimi saxlayacağıq. Zirvələrin vəziyyətini saxlamaq üçün $used$ massivindən istifadə edəcəyik:

• used[i] = 0, əgər zirvə $i$ hələ ziyarət edilməyibsə (zirvə ağdır);

• used[i] = 1, əgər zirvə $i$ ziyarət olunub, amma onun işlənməsi hələ tam deyil (zirvə bozdur);

• used[i] = 2, əgər zirvə $i$ artıq işlənibsə (zirvə qaradır);

Dərinlik üzrə axtarış icrası zamanı zirvələri $top$ massivinə onların işlənməsi tamamlanma sırasına görə əlavə edəcəyik. Alqoritm tamamlandıqdan sonra $top$ massivi zirvələri əks topoloji sıralamada saxlayacaq.

vector<vector<int> > g;
vector<int> used, top;

dfs funksiyası qrafı dərinlik üzrə axtarışı yerinə yetirir, zirvə $v$-dən başlayaraq.

void dfs(int v)
{

Zirvə $v$-yə giririk və onu boz rəngdə işarələyirik.

  used[v] = 1;

Zirvə $v$-dən keçməklə çıxılan bütün zirvələri $to$ seçirik.

  for (int to : g[v])
  {

Əgər yönlənmiş kənar (v, to) boz zirvəyə aparırsa, bu qrafda döngənin olduğunu göstərir. Bu halda flag = 1 qoyuruq.

    if (used[to] == 1) flag = 1;

Əgər $to$ zirvəsi hələ ziyarət edilməyibsə, ondan rekursiv olaraq dərinlik üzrə axtarışı işə salırıq.

    if (used[to] == 0) dfs(to);
  }

Zirvə $v$-nin işlənməsini tamamlayırıq. Onu qara işarələyirik və $top$ massivinə əlavə edirik.

  used[v] = 2;
  top.push_back(v);
}

Əsas proqram hissəsi. Giriş məlumatlarını oxuyuruq. Qrafın əlaqə siyahısını qururuq.

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

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

Yönləndirilmiş qrafı dərinlik üzrə axtarışı icra edirik.

flag = 0;
for(i = 1; i <= n; i++)
  if (used[i] == 0) dfs(i);

Əgər dərinlik üzrə axtarış zamanı döngə aşkar edilərsə (flag = 1 qoyulub), $-1$ çap edirik.

if (flag == 1) printf("-1");
else

Əks halda zirvələri qrafın $top$ massivinə əlavə olunma sırasının əksinə çap edirik.

  for(i = top.size() - 1; i >= 0; i--)
    printf("%d ",top[i]);

printf("\n");

Alqoritmin reallaşdırılması — Kan

Giriş qrafı əlaqə siyahısı $g$-də saxlanılır.

Zirvələrin hər biri üçün gələn kənarların sayını InDegree massivində saxlayırıq.

Topoloji sıralamanın nəticəsini $top$ massivinə əlavə edirik.

vector<vector<int> > g;
vector<int> InDegree, top;
deque<int> q;

Zirvələrin sayını $n$ və kənarların sayını $m$ oxuyuruq.

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

Qrafın $m$ kənarını oxuyuruq.

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

Hər kənar üçün $(a,b)$ InDegree[b]-ni $1$ artırırıq.

  InDegree[b]++;
}

Giriş dərəcəsi sıfır olan bütün zirvələri $q$ növbəsinə əlavə edirik.

for(i = 1; i < InDegree.size(); i++)
  if (!InDegree[i]) q.push_back(i);

Alqoritmi çalışdırmağa davam edirik, növbə $q$ boş olmadığı müddətcə.

while(!q.empty())
{

$q$ növbəsindən zirvə $v$ götürərək onu topoloji ardıcıllığın sonuna əlavə edirik.

  v = q.front(); q.pop_front();
  top.push_back(v);

(v, to) kənarlarını qrafdan silirik. Hər belə kənar üçün zirvə $to$-nun gələn dərəcəsini azaldırıq.

  for (int to : g[v])
  {
    InDegree[to]--;

Əgər zirvə $to$-nun gələn dərəcəsi sıfıra bərabər olarsa, onu növbəyə əlavə edirik. Daha sonra o, topoloji ardıcıllığın siyahısına qoyulacaq.

    if (!InDegree[to]) q.push_back(to);
  }
}

Əgər $top$ massivinə bütün $n$ zirvələr əlavə edilməyibsə, qraf döngə ehtiva edir və topoloji sıralama etmək mümkün deyil.

if (top.size() < n) 
  printf("-1\n");
else
{

Əks halda, qrafın zirvələrini topoloji sıralama düzenində çap edirik.

  for (int x : top) printf("%d ", x);
  printf("\n");
}

Java reallaşdırılması — dərinlik üzrə axtarış

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

public class Main
{
  static ArrayList<ArrayList<Integer>> g;
  static ArrayList<Integer> top = new ArrayList<Integer>();
  static int used[];
  static int n, m, flag = 0;
    
  static void dfs(int v)
  {
    used[v] = 1;
    for(int i = 0; i < g.get(v).size(); i++)
    {
      int to = g.get(v).get(i);
      if (used[to] == 1) flag = 1;
      if (used[to] == 0) dfs(to);
    }
    used[v] = 2;
    top.add(v);
  }
    
  public static void main(String[] args)
  {
    FastScanner con = new FastScanner(System.in);
    n = con.nextInt();
    m = con.nextInt();
    g = new ArrayList<ArrayList<Integer>>();
    used = 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);
    }
      
    for(int i = 1; i <= n; i++)
      if (used[i] == 0) dfs(i);
      
    if (flag == 1) System.out.println("-1");
    else
      for(int i = top.size() - 1; i >= 0; i--)
        System.out.print(top.get(i) + " ");
    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 reallaşdırılması — Kan

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]++;
    }
      
    Queue<Integer> q = new LinkedList<Integer>();
    for(int i = 1; i <= n; i++)
      if (InDegree[i] == 0) q.add(i);

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

Python reallaşdırılması — dərinlik üzrə axtarış

Rekursiya dərinliyini artıraq.

import sys
sys.setrecursionlimit(10000)

dfs funksiyası qrafı dərinlik üzrə axtarışı yerinə yetirir, zirvə $v$-dən başlayaraq.

def dfs(v):

Zirvə $v$-yə giririk və onu boz rəngdə işarələyirik.

  used[v] = 1

Zirvə $v$-dən keçməklə çıxılan bütün zirvələri $to$ seçirik.

  for to in g[v]:

Əgər yönlənmiş kənar (v, to) boz zirvəyə aparırsa, bu qrafda döngənin olduğunu göstərir. Bu halda flag = 1 qoyuruq.

    if used[to] == 1:
      global flag
      flag = 1

Əgər $to$ zirvəsi hələ ziyarət edilməyibsə, ondan rekursiv olaraq dərinlik üzrə axtarışı işə salırıq.

    if used[to] == 0:
      dfs(to)

Zirvə $v$-nin işlənməsini tamamlayırıq. Onu qara işarələyirik və $top$ massivinə əlavə edirik.

  used[v] = 2
  top.append(v)

Əsas proqram hissəsi. Zirvələrin sayını $n$ və kənarların sayını $m$ oxuyuruq.

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

Giriş qrafı əlaqə siyahısı $g$-də saxlanılır. $used$ siyahısını elan edirik.

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

Kənarların siyahısını oxuyuruq. Qrafın əlaqə siyahısını qururuq.

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

Yönləndirilmiş qrafı dərinlik üzrə axtarışı icra edirik.

flag = 0
top = []
for i in range(1, n + 1):
  if used[i] == 0: dfs(i)

Əgər dərinlik üzrə axtarış zamanı döngə aşkar edilərsə (flag = 1 qoyulub), $-1$ çap edirik.

if flag == 1:
  print("-1")
else:

Əks halda zirvələri qrafın $top$ massivinə əlavə olunma sırası əks tərzdə çap edirik.

  for i in range(len(top) - 1, -1, -1):
    print(top[i], end=" ")
  print()

Python reallaşdırılması – Kan alqoritmi

Növbə $q$ elan edək.

from collections import deque
q = deque()

Zirvələrin sayını $n$ və kənarların sayını $m$ oxuyuruq.

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

Giriş qrafı əlaqə siyahısı $g$-də saxlanılır.

Zirvələrin hər biri üçün gələn kənarların sayını InDegree siyahısında saxlayırıq.

Topoloji sıralamanın nəticəsini $top$ siyahısına əlavə edirik.

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

Qrafın $m$ kənarını oxuyuruq.

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

Hər kənar üçün $(a,b)$ InDegree[b]-ni $1$ artırırıq.

  InDegree[b] += 1

Giriş dərəcəsi sıfır olan bütün zirvələri $q$ növbəsinə əlavə edirik.

for i in range(1, len(InDegree)):
  if not InDegree[i]: q.append(i)

Alqoritmi çalışdırmağa davam edirik, növbə $q$ boş olmadığı müddətcə.

while q:

$q$ növbəsindən zirvə $v$ götürərək onu topoloji ardıcıllığın sonuna əlavə edirik.

  v = q.popleft()
  top.append(v)

(v, to) kənarlarını qrafdan silirik. Hər belə kənar üçün zirvə $to$-nun gələn dərəcəsini azaldırıq.

  for to in g[v]:
    InDegree[to] -= 1

Əgər zirvə $to$-nun gələn dərəcəsi sıfıra bərabər olarsa, onu növbəyə əlavə edirik. Daha sonra o, topoloji ardıcıllığın siyahısına qoyulacaq.

    if not InDegree[to]: q.append(to)

Əgər $top$ massivinə bütün $n$ zirvələr əlavə edilməyibsə, qraf döngə ehtiva edir və topoloji sıralama etmək mümkün deyil.

if len(top) < n:
  print("-1")
else:

Əks halda, qrafın zirvələrini topoloji sıralama düzenində çap edirik.

  for i in top:
    print(i, end=" ")
  print()