Corso di Ottimizzazione Combinatoria (IN440)

Esercizi e sorgenti dei programmi

Ordinamento topologico dei vertici di un grafo orientato aciclico

Il sort topologico dell'insieme dei vertici di un grafo può essere definito solo se il grafo è orientato e non contiene cicli; in tal caso possiamo ordinare l'insieme dei vertici V(G) in base al seguente principio: se (u,v) ∈ E(G) allora u < v.

Per ottenere un ordinamento topologico dell'insieme dei vertici del grafo, in questo breve programma, si suppone che il grafo fornito in input sia orientato e aciclico (un DAG - directed acyclic graph); si utilizza il seguente algoritmo implementato nella funzione sortTopologico definita nella libreria grafi.c:

  1. definisce una coda Q inizialmente vuota
  2. calcola il grafo GT trasposto di G
  3. fintanto che esiste in GT un vertice v con grado uscente nullo ripete i seguenti passi:
    1. elimina da GT tutti gli spigoli (u,v)∈ E(GT) entranti in v
    2. elimina da GT il vertice v
    3. aggiunge nella coda Q il vertice v
  4. fine-ciclo
  5. la coda Q contiene i vertici di G in ordine topologico.

La compilazione del programma richiede l'uso della libreria grafi.c.

/* ** sortTopologico.c ** ** Letto in input un grafo orientato aciclico, costruisce una lista ** con i vertici del grafo in ordine topologico. ** ** #(@) 20081109 (liverani@mat.uniroma3.it) */
#include <stdlib.h> #include <stdio.h> #include "grafi.h" int main (void){ grafo G; elementoLista *p; printf("Inserire le liste di adiacenza del grafo orientato aciclico:\n"); leggiGrafo(&G); printf("Grafo originale: \n"); stampaGrafo(G); p = sortTopologico(G); printf("\nVertici del grafo in ordine topologico:\n"); stampaLista(p); return(0); }

Università degli Studi Roma Tre - Dipartimento di Matematica e Fisica - Corso di laurea in Matematica - Corso di Ottimizzazione Combinatoria (IN440)

Author: Marco Liverani - Last modified: Saturday September 05, 2020 - Document URI: https://www.mat.uniroma3.it/users/liverani/IN440/sortTopologico.shtml