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:
- definisce una coda Q inizialmente vuota
- calcola il grafo GT trasposto di G
- fintanto che esiste in GT un vertice v con grado uscente nullo ripete i seguenti passi:
- elimina da GT tutti gli spigoli (u,v)∈ E(GT) entranti in v
- elimina da GT il vertice v
- aggiunge nella coda Q il vertice v
- fine-ciclo
- 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); }