Ordinamento Topologico (Editoriale)

Un ordinamento topologico di un grafo orientato è un ordinamento dei suoi vertici tale che per ogni arco $u \to v$ u \to v il vertice $u$ compare nella sequenza prima del vertice $v$ . Un ordinamento topologico esiste se e solo se il grafo non contiene cicli orientati (cioè è aciclico).

Risolviamo il problema con la ricerca in profondità. A ogni vertice viene assegnato un colore:

bianco — il vertice non è ancora stato visitato;
grigio — il vertice è stato visitato, ma la sua elaborazione non è terminata (si trova nello stack di ricorsione corrente);
nero — il vertice e tutti i vertici raggiungibili da esso sono stati completamente elaborati.

Inizialmente tutti i vertici sono bianchi. Avviamo una ricerca in profondità da ogni vertice bianco. Entrando in un vertice lo coloriamo di grigio; uscendone lo coloriamo di nero e in quel momento lo aggiungiamo a una lista. L'ordine dei vertici nell'ordinamento topologico è l'inverso dell'ordine in cui diventano neri: il primo vertice elaborato completamente sarà l'ultimo nell'ordinamento, e l'ultimo vertice elaborato sarà il primo.

Rilevamento dei cicli. Se durante la visita incontriamo un arco che porta a un vertice grigio, il grafo contiene un ciclo e l'ordinamento topologico è impossibile — stampiamo $- 1$ .

Complessità. Ogni vertice e ogni arco vengono elaborati esattamente una volta, quindi il tempo di esecuzione è $O (n + m)$ O(n + m).

Esempio

Il grafo presentato nell'esempio ha la seguente forma:

Accanto a ogni vertice $v$ poniamo le etichette $d [v] / f [v]$ d[v] / f[v], dove $d [v]$ è l'istante in cui inizia l'elaborazione del vertice e $f [v]$ è l'istante in cui la sua elaborazione termina. I vertici ordinati topologicamente sono disposti in ordine decrescente dei valori $f [v]$ .

Implementazione dell'algoritmo

Poiché il numero di vertici del grafo è grande, memorizziamo il grafo come lista di adiacenza $g$ . Per tenere traccia dello stato dei vertici usiamo l'array $u se d$ :

$u se d [i] = 0$ used[i] = 0, se il vertice $i$ non è ancora stato visitato (il vertice è bianco);
$u se d [i] = 1$ used[i] = 1, se il vertice $i$ è stato visitato, ma la sua elaborazione non è ancora terminata (il vertice è grigio);
$u se d [i] = 2$ used[i] = 2, se il vertice $i$ è stato elaborato (il vertice è nero);

Durante l'esecuzione della ricerca in profondità aggiungiamo i vertici all'array $t o p$ nell'ordine in cui termina la loro elaborazione. Al termine dell'algoritmo l'array $t o p$ conterrà i vertici nell'ordine inverso rispetto all'ordinamento topologico.

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

La funzione dfs esegue una ricerca in profondità a partire dal vertice $v$ .

void dfs(int v)
{

Entriamo nel vertice $v$ e lo coloriamo di grigio.

  used[v] = 1;

Scorriamo tutti i vertici $t o$ raggiungibili dal vertice $v$ .

  for (int to : g[v])
  {

Se l'arco orientato $(v, t o)$ (v, to) porta a un vertice grigio, il grafo contiene un ciclo. In questo caso poniamo $f l a g = 1$ flag = 1.

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

Se il vertice $t o$ non è ancora stato visitato, avviamo ricorsivamente da esso una ricerca in profondità.

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

Terminiamo l'elaborazione del vertice $v$ . Lo coloriamo di nero e lo aggiungiamo in fondo all'array $t o p$ .

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

La parte principale del programma. Leggiamo i dati di input e costruiamo la lista di adiacenza del grafo.

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

C++

Eseguiamo una ricerca in profondità sul grafo orientato.

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

Se durante la ricerca in profondità è stato rilevato un ciclo ( $f l a g = 1$ flag = 1), stampiamo $- 1$ .

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

Altrimenti stampiamo i vertici del grafo nell'ordine inverso rispetto a quello in cui sono stati aggiunti all'array $t o p$ .

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

printf("\n");

Implementazione dell'algoritmo — Kahn

Memorizziamo il grafo di input nella lista di adiacenza $g$ .

I gradi entranti dei vertici sono memorizzati nell'array $I n D e g r ee$ InDegree.

Il risultato dell'ordinamento topologico è memorizzato nell'array $t o p$ .

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

Leggiamo il numero di vertici $n$ e il numero di archi $m$ .

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

Leggiamo gli $m$ archi del grafo.

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

Per ogni arco $(a, b)$ aumentiamo $I n D e g r ee [b]$ InDegree[b] di $1$ .

  InDegree[b]++;
}

Tutti i vertici con grado entrante zero vengono inseriti nella coda $q$ .

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

Proseguiamo l'algoritmo finché la coda $q$ non è vuota.

while(!q.empty())
{

Estraiamo dalla coda il vertice $v$ e lo aggiungiamo in fondo alla lista dell'ordinamento topologico.

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

Rimuoviamo dal grafo gli archi $(v, t o)$ (v, to). Per ciascuno di questi archi diminuiamo il grado entrante del vertice $t o$ .

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

Se il grado entrante del vertice $t o$ diventa zero, lo inseriamo nella coda. In seguito verrà aggiunto alla lista dell'ordinamento topologico.

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

Se non tutti gli $n$ vertici sono stati aggiunti all'array $t o p$ , il grafo contiene un ciclo e l'ordinamento topologico è impossibile.

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

Altrimenti stampiamo i vertici del grafo in ordine topologico.

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

Implementazione in Java — ricerca in profondità

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

Implementazione in Java — 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());
  }
}

Java

Implementazione in Python — ricerca in profondità

Aumentiamo la profondità massima di ricorsione.

import sys
sys.setrecursionlimit(10000)

La funzione dfs esegue una ricerca in profondità a partire dal vertice $v$ .

def dfs(v):

Entriamo nel vertice $v$ e lo coloriamo di grigio.

  used[v] = 1

Scorriamo tutti i vertici $t o$ raggiungibili dal vertice $v$ .

  for to in g[v]:

Se l'arco orientato $(v, t o)$ (v, to) porta a un vertice grigio, il grafo contiene un ciclo. In questo caso poniamo $f l a g = 1$ flag = 1.

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

Se il vertice $t o$ non è ancora stato visitato, avviamo ricorsivamente da esso una ricerca in profondità.

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

Terminiamo l'elaborazione del vertice $v$ . Lo coloriamo di nero e lo aggiungiamo in fondo all'array $t o p$ .

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

La parte principale del programma. Leggiamo il numero di vertici $n$ e il numero di archi $m$ .

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

Memorizziamo il grafo di input nella lista di adiacenza $g$ . Dichiariamo la lista $u se d$ .

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

Leggiamo la lista degli archi e costruiamo la lista di adiacenza del grafo.

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

Eseguiamo una ricerca in profondità sul grafo orientato.

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

Se durante la ricerca in profondità è stato rilevato un ciclo ( $f l a g = 1$ flag = 1), stampiamo $- 1$ .

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

Altrimenti stampiamo i vertici del grafo nell'ordine inverso rispetto a quello in cui sono stati aggiunti all'array $t o p$ .

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

Implementazione in Python — Kahn

Dichiariamo la coda $q$ .

from collections import deque
q = deque()

Leggiamo il numero di vertici $n$ e il numero di archi $m$ .

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

Memorizziamo il grafo di input nella lista di adiacenza $g$ .

I gradi entranti dei vertici sono memorizzati nella lista $I n D e g r ee$ InDegree.

Il risultato dell'ordinamento topologico è memorizzato nella lista $t o p$ .

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

Leggiamo gli $m$ archi del grafo.

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

Per ogni arco $(a, b)$ aumentiamo $I n D e g r ee [b]$ InDegree[b] di $1$ .

  InDegree[b] += 1

Tutti i vertici con grado entrante zero vengono inseriti nella coda $q$ .

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

Proseguiamo l'algoritmo finché la coda $q$ non è vuota.

while q:

Estraiamo dalla coda il vertice $v$ e lo aggiungiamo in fondo alla lista dell'ordinamento topologico.

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

Rimuoviamo dal grafo gli archi $(v, t o)$ (v, to). Per ciascuno di questi archi diminuiamo il grado entrante del vertice $t o$ .

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

Se il grado entrante del vertice $t o$ diventa zero, lo inseriamo nella coda. In seguito verrà aggiunto alla lista dell'ordinamento topologico.

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

Se non tutti gli $n$ vertici sono stati aggiunti all'array $t o p$ , il grafo contiene un ciclo e l'ordinamento topologico è impossibile.

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

Altrimenti stampiamo i vertici del grafo in ordine topologico.

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