Esercizi e sorgenti dei programmi

Componenti Fortemente Connesse di un grafo orientato

Implementazione dell'algoritmo per il calcolo delle componenti fortemente connesse di un grafo orientato G. L'algoritmo può essere riassunto nei seguenti passi:

  1. Esegue una visita in profondità (DFS) di G e calcola i tempi di fine visita (in realtà inserisce i vertici di G in una pila in base all'ordine di completamento della visita)
  2. Calcola le liste di adiacenza del grafo trasposto GT, ottenuto invertendo il verso degli spigoli di G
  3. Esegue una visita in profondità del grafo trasposto, considerando i vertici nell'ordine decrescente di tempo di completamento della visita calcolato al passo 1. Gli alberi di visita individuati in GT sono le componenti fortemente connesse di G

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

/* * cfc.c * * Componenti Fortemente Connesse di un grafo orientato. * * #(@) 20081020 (liverani@mat.uniroma3.it) */
#include <stdlib.h> #include <stdio.h> #include "grafi.h" void visita(grafo G, elementoLista **f, int i, int c[]) { elementoLista *p; c[i] = 1; p = G.V[i]; while (p != NULL) { if (c[p->info] == 0) { visita(G, f, p->info, c); } p = p->next; } *f = impila(*f, i); return; } void dfs(grafo G, elementoLista **f) { int *c, i; c = malloc(sizeof(int)*(G.n+1)); for (i=1; i<=G.n; i++) { c[i] = 0; } for (i=1; i<=G.n; i++) { if (c[i] == 0) { visita(G, f, i, c); } } return; } void visitaBis(grafo G, int i, int c[]) { elementoLista *p; c[i] = 1; p = G.V[i]; printf("%d ", i); while (p != NULL) { if (c[p->info] == 0) { visitaBis(G, p->info, c); } p = p->next; } return; }
/* * funzione principale * * Calcola le componenti fortemente connesse del grafo orientato G * utilizzando il seguente algoritmo: * 1. Esegue una visita in profondita' (DFS) di G e calcola i tempi * di fine visita (in realta' inserisce i vertici di G in una pila * in base all'ordine di fine della visita) * 2. Calcola le liste di adiacenza del grafo trasposto GT, ottenuto * invertendo il verso degli spigoli di G * 3. Esegue una visita in profondita' del grafo trasposto, considerando * i vertici nell'ordine decrescente di tempo di completamento della * visita calcolato al passo 1. Gli alberi di visita individuati in GT * sono le componenti fortemente connesse di G. */
int main(void) { grafo G, GT; elementoLista *f; int i, *c, cont = 1; leggiGrafo(&G); printf("\nListe di adiacenza del grafo G:\n"); stampaGrafo(G);
/* PASSO 1 */
dfs(G, &f); printf("\nOrdine dei vertici di G in base al tempo di fine visita:\n"); stampaLista(f);
/* PASSO 2 */
grafoTrasposto(G, &GT); printf("\nListe di adiacenza del grafo trasposto GT:\n"); stampaGrafo(GT);
/* PASSO 3 */
printf("\nComponenti fortemente connesse del grafo G:\n"); c = malloc(sizeof(int)*(G.n+1)); for (i=1; i<=GT.n; i++) c[i] = 0; while (f != NULL) { if (c[f->info] == 0) { printf(" Componente n.%d = { ", cont++); visitaBis(GT, f->info, c); printf("}\n"); } f = f->next; } return(0); }