Topolojik Sıralama (Editoryal)

Yönlü bir grafın topolojik sıralaması, düğümlerinin öyle bir sıralamasıdır ki her u \to v kenarı için $u$ düğümü dizide $v$ düğümünden önce gelir. Topolojik sıralama ancak ve ancak graf yönlü döngü içermiyorsa (yani döngüsüzse) vardır.

Problemi derinlik öncelikli arama ile çözeriz. Her düğüme bir renk atanır:

• beyaz — düğüm henüz ziyaret edilmemiştir;

• gri — düğüm ziyaret edilmiştir, ancak işlenmesi bitmemiştir (mevcut özyineleme yığınındadır);

• siyah — düğüm ve ondan erişilebilen tüm düğümler tamamen işlenmiştir.

Başlangıçta tüm düğümler beyazdır. Her beyaz düğümden bir derinlik öncelikli arama başlatırız. Bir düğüme girerken onu griye boyarız; çıkarken siyaha boyar ve o anda bir listeye ekleriz. Topolojik sıralamadaki düğümlerin sırası, düğümlerin siyaha dönme sırasının tersidir: tamamen işlenen ilk düğüm sıralamada son, en son işlenen düğüm ise ilk olur.

Döngü tespiti. Dolaşma sırasında gri bir düğüme giden bir kenarla karşılaşırsak, graf bir döngü içerir ve topolojik sıralama imkânsızdır — $-1$ yazdırırız.

Karmaşıklık. Her düğüm ve her kenar tam olarak bir kez işlenir, bu yüzden çalışma süresi O(n + m)'dir.

Örnek

Örnekte verilen graf aşağıdaki gibidir:

Her $v$ düğümünün yanına d[v] / f[v] etiketlerini yerleştiririz; burada $d[v]$ düğümün işlenmeye başladığı an, $f[v]$ ise işlenmesinin bittiği andır. Topolojik olarak sıralanmış düğümler $f[v]$ değerlerinin azalan sırasına göre dizilir.

Algoritmanın gerçekleştirilmesi

Graftaki düğüm sayısı büyük olduğundan grafı $g$ komşuluk listesi olarak saklarız. Düğümlerin durumunu takip etmek için $used$ dizisini kullanırız:

• used[i] = 0, eğer $i$ düğümü henüz ziyaret edilmediyse (düğüm beyazdır);

• used[i] = 1, eğer $i$ düğümü ziyaret edildiyse, ancak işlenmesi henüz bitmediyse (düğüm gridir);

• used[i] = 2, eğer $i$ düğümü işlendiyse (düğüm siyahtır);

Derinlik öncelikli arama sırasında düğümleri, işlenmelerinin bittiği sırayla $top$ dizisine ekleriz. Algoritma bittiğinde $top$ dizisi düğümleri topolojik sıralamanın ters sırasıyla içerecektir.

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

dfs fonksiyonu $v$ düğümünden başlayarak derinlik öncelikli arama yapar.

void dfs(int v)
{

$v$ düğümüne gireriz ve onu griye boyarız.

  used[v] = 1;

$v$ düğümünden erişilebilen tüm $to$ düğümlerini dolaşırız.

  for (int to : g[v])
  {

(v, to) yönlü kenarı gri bir düğüme gidiyorsa, grafta bir döngü vardır. Bu durumda flag = 1 olarak ayarlarız.

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

$to$ düğümü henüz ziyaret edilmediyse, ondan özyinelemeli olarak derinlik öncelikli arama başlatırız.

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

$v$ düğümünün işlenmesini bitiririz. Onu siyaha boyar ve $top$ dizisinin sonuna ekleriz.

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

Programın ana kısmı. Giriş verilerini okur ve grafın komşuluk listesini oluştururuz.

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ü graf üzerinde derinlik öncelikli arama yaparız.

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

Derinlik öncelikli arama sırasında bir döngü tespit edildiyse (flag = 1), $-1$ yazdırırız.

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

Aksi hâlde grafın düğümlerini $top$ dizisine eklenme sıralarının tersine göre yazdırırız.

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

printf("\n");

Algoritmanın gerçekleştirilmesi — Kahn

Giriş grafını $g$ komşuluk listesinde saklarız.

Düğümlerin giriş dereceleri InDegree dizisinde saklanır.

Topolojik sıralamanın sonucu $top$ dizisinde saklanır.

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

Düğüm sayısı $n$ ve kenar sayısı $m$ okunur.

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

Grafın $m$ kenarını okuruz.

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

Her $(a,b)$ kenarı için InDegree[b] değerini $1$ artırırız.

  InDegree[b]++;
}

Giriş derecesi sıfır olan tüm düğümler $q$ kuyruğuna eklenir.

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

$q$ kuyruğu boşalana kadar algoritmaya devam ederiz.

while(!q.empty())
{

Kuyruktan $v$ düğümünü çıkarır ve topolojik sıralama listesinin sonuna ekleriz.

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

(v, to) kenarlarını graftan kaldırırız. Bu kenarların her biri için $to$ düğümünün giriş derecesini azaltırız.

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

$to$ düğümünün giriş derecesi sıfır olursa, onu kuyruğa ekleriz. Daha sonra topolojik sıralama listesine yerleştirilecektir.

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

$n$ düğümün tamamı $top$ dizisine eklenmediyse, graf bir döngü içerir ve topolojik sıralama imkânsızdır.

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

Aksi hâlde grafın düğümlerini topolojik sırayla yazdırırız.

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

Java gerçekleştirmesi — derinlik öncelikli arama

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 gerçekleştirmesi — Kahn

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 gerçekleştirmesi — derinlik öncelikli arama

Özyineleme derinliği sınırını artırırız.

import sys
sys.setrecursionlimit(10000)

dfs fonksiyonu $v$ düğümünden başlayarak derinlik öncelikli arama yapar.

def dfs(v):

$v$ düğümüne gireriz ve onu griye boyarız.

  used[v] = 1

$v$ düğümünden erişilebilen tüm $to$ düğümlerini dolaşırız.

  for to in g[v]:

(v, to) yönlü kenarı gri bir düğüme gidiyorsa, grafta bir döngü vardır. Bu durumda flag = 1 olarak ayarlarız.

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

$to$ düğümü henüz ziyaret edilmediyse, ondan özyinelemeli olarak derinlik öncelikli arama başlatırız.

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

$v$ düğümünün işlenmesini bitiririz. Onu siyaha boyar ve $top$ dizisinin sonuna ekleriz.

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

Programın ana kısmı. Düğüm sayısı $n$ ve kenar sayısı $m$ okunur.

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

Giriş grafını $g$ komşuluk listesinde saklarız. $used$ listesini tanımlarız.

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

Kenar listesini okur ve grafın komşuluk listesini oluştururuz.

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

Yönlü graf üzerinde derinlik öncelikli arama yaparız.

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

Derinlik öncelikli arama sırasında bir döngü tespit edildiyse (flag = 1), $-1$ yazdırırız.

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

Aksi hâlde grafın düğümlerini $top$ dizisine eklenme sıralarının tersine göre yazdırırız.

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

Python gerçekleştirmesi — Kahn

$q$ kuyruğunu tanımlarız.

from collections import deque
q = deque()

Düğüm sayısı $n$ ve kenar sayısı $m$ okunur.

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

Giriş grafını $g$ komşuluk listesinde saklarız.

Düğümlerin giriş dereceleri InDegree listesinde saklanır.

Topolojik sıralamanın sonucu $top$ listesinde saklanır.

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

Grafın $m$ kenarını okuruz.

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

Her $(a,b)$ kenarı için InDegree[b] değerini $1$ artırırız.

  InDegree[b] += 1

Giriş derecesi sıfır olan tüm düğümler $q$ kuyruğuna eklenir.

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

$q$ kuyruğu boşalana kadar algoritmaya devam ederiz.

while q:

Kuyruktan $v$ düğümünü çıkarır ve topolojik sıralama listesinin sonuna ekleriz.

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

(v, to) kenarlarını graftan kaldırırız. Bu kenarların her biri için $to$ düğümünün giriş derecesini azaltırız.

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

$to$ düğümünün giriş derecesi sıfır olursa, onu kuyruğa ekleriz. Daha sonra topolojik sıralama listesine yerleştirilecektir.

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

$n$ düğümün tamamı $top$ dizisine eklenmediyse, graf bir döngü içerir ve topolojik sıralama imkânsızdır.

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

Aksi hâlde grafın düğümlerini topolojik sırayla yazdırırız.

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