Grafi

La struttura dati più naturale per rappresentare un insieme di oggetti legati da una generica relazione tra loro è il grafo. Formalmente un grafo è una coppia con un insieme di nodi ed un insieme di archi. Se un grafo ha nodi esso ha al più archi.

Due nodi collegati da un arco si dicono adiacenti. Un cammino tra due nodi e è un insieme di archi di cui il primo ha origine in , l'ultimo termina in e ogni nodo compare almeno una volta come destinazione di un arco e come sorgente.

È possibile implementare un grafo con una lista di adiacenza o matrice di adiacenza.

Una lista di adiacenza è un vettore di liste lungo , indicizzato dai nomi dei nodi. Ogni lista contiene i nodi adiacenti all'indice della sua desta. Ha complessità spaziale . Per determinare se un arco appartiene al grafo ha complessità , e per determinare il numero di archi uscenti di un nodo ha complessità .

Una matrice di adiacenza è una matrice di valori booleani con righe e colonne indicizzate dai nomi dei nodi. La cella alla riga colonna contiene se l'arco è presente nel grafo, altrimenti. Ha complessità spaziale . Per determinare se un arco appartiene al grafo ha complessità , e per determinare il numero di archi uscenti di un nodo ha complessità .

Come per le visite degli alberi, è possibile stampare i nodi in una visita di un grafo, VisitaAmpiezza si può quindi trasformare in algoritmo di ricerca. Ha complessità totale .

VisitaAmpiezza(G,s)
	for each n in V except s
		n.color <- white
		n.dist <- infinity
	
	s.color <- grey
	s.dist <- 0
	Q <- 0
	Enqueue(Q,s)
	
	while !isEmpty(Q)
		curr <- Dequeue(Q)
		for each v in curr.adiacenti
			if v.color = while
				v.color <- grey
				v.dist <- curr.dist + 1
				Enqueue(Q,v)
		curr.color <- black
Copy

È anche possibile visitare in profondità, dove, diversamente dalla visita in ampiezza visitiamo prima i nodi adiacenti a quello dato, e poi il nodo stesso.

È detta componente connessa di un grafo un insieme di nodi tali per cui esiste un cammino tra ogni coppia di essi, ma nessuno di essi è connesso a nodi non in . Individuare le componenti connesse in un grafo equivale ad etichettare i nodi con lo stesso valore se appartengono alla stessa componente. Ha complessità .

ComponentiConnesse(G)
	for each v in V
		v.etichetta <- -1
	eti <- 1
	for each v in V
		if v.etichetta = -1
			VisitaEdEtichetta(G,v,eti)
			eti <- eti + 1
Copy

Dove il metodo VisitaEdEtichetta funziona come VisitaAmpiezza o VisitaProfondità ma imposta a eti il campo etichetta del nodo visitato.

Dato un grafo orientato, definiamo il predecessore di un nodo un nodo tale per cui esiste un cammino da a .
Un valore utile da calcolare per un grafo orientato aciclico è il cosiddetto ordinamento topologico. L'ordinamento topologico è una sequenza di nodi del grafo tale per cui nessun nodo compare prima di un suo predecessore. L'ordinamento topologico non è unico.

Se il grafo non è connesso le componenti connesse possono essere ordinate in qualunque modo l'una rispetto all'altra.

VisitaProfOT(G,s,L)
	s.color <- grey
	for each v in curr.adiacenti
		if v.color = white
			VisitaProfOT(G,v,L)
	s.color <- black
	PushFront(L,s)

OrdinamentoTopologico(G)
	for each v in V
		v.color <- white
	
	for each v in V
		if v.color = white
			VisitaProfOT(G,v,L)
	return L
Copy

L'algoritmo di Dijkstra trova, dato un grafo orientato e un suo nodo i percorsi più previ da un nodo a qualunque altro. Funziona sia su un grafo classico che su un grafo pesato.

Funziona inserendo ogni in un insieme , dopo aver impostato il suo attributo distanza a e il v.pred a NIL. Inserisco in dopo aver impostato s.dist <- 0 e s.pred <- NIL. Quindi, fino a quando non è vuoto, estraggo il nodo c con dist minima e controllo per ogni adiacente a se hanno distanza minore di c.dist + peso(c,a). Se questo accade imposto a.pred <- c e a.dist <- c.dist + peso(c,a).

È possibile migliorare la complessità memorizzando l'insieme come una coda con priorità usando un min-heap. Questo algoritmo ha complessità .

DijkstraQueue(G,s)
	Q <- 0
	s.dist <- 0
	
	for each v in V
		if v != s
			v.dist <- infinity
			v.pred <- NIL
		AccodaPri(Q,v,v.dist)
	
	while Q != 0
		u <- CancellaMin(Q)
		for each v in u.succ
			ndis <- u.dist + peso(u,v)
			if v.dist > ndis
				v.dist <- ndis
				u.prev <- u
				DecrementaPri(Q,v,ndis)
Copy

Dato un grafo orientato, in cui ogni nodo ha un solo successore, l'algoritmo di Floyd determina, a partire da un nodo iniziale se il cammino genera un ciclo. Ha complessità , dove è la lunghezza della coda che precede il ciclo, è la lunghezza del ciclo e .

FloydLT(G,x)
	t <- x.succ
	l <- x.succ.succ
	
	while l != t
		t <- t.succ
		l <- l.succ.succ
	
	T <- 0
	t <- x
	
	while l != t
		t <- t.succ
		l <- l.succ
		T <- T + 1
	
	l <- t
	C <- 0
	while l != t
		l <- l.succ
		C <- C + 1
	
	return T,C
Copy