10 aprile 2024 - esercizio 1

[CuriousCI]

Sia $G = (V, E)$ un grafo non diretto, allora si definisce il diametro di $G, diam(G) = max \set{u,v \in V, d(u, v)}$, il massimo della
distanza tra due qualsiasi vertici di $G$. Fornire un algoritmo in pseudo-codice che restituisca il diametro di un grafo G, nel caso in cui $G$ sia un albero. È possibile ottenere una soluzione con tempo di esecuzione $O(|V|)$?

[LeoCosta02]

//Sia G un grafo non diretto, allora si definisce il diametro di G  , il massimo della distanza tra due qualsiasi vertici di G
// Fornire un algoritmo in pseudo-codice che restituisca il diametro di un grafo G, nel caso in cui 
 //sia un albero

 //SOLUZIONE: Come viene proposto nella soluzione, in input riceviamo un nodo qualsiasi dell'albero perciò
 // calcolo prima la distanza massima dal vertice dato in input con un vertice dell'albero e poi 
 //calcolo a sua volta la distanza massima di quel vertice con i nodi dell albero e trovo cosi il diametro 
 Diamentro(G){
    int vis[n] :inizializzato a 0 
    int dist[n]: inizializzatoa  0
     int  max=0
// nell'algoritmo considero un solo albero quindi il grafo è connesso altrimenti se ho più componenti il diametro è infinito
    u:vert(G)
    max=DFS(G,u,max)
    u_local_max=compare(max,dist)// confronta max con ogni elemento del vettore dist e return indice dove max==dist[i]
    for (int i=0;i<n;i++){
        vis[n]=0
        dist[n]=0
    }
    diametro=DFS(G,u_local_max,max)
    return diametro
 }

 DFS(G,x,max,indice){
    vis[x]=1
    for each(w appartenente ad adiacente di x){
        if(vis[w]==0){
           dist[w]= DFS(G,w,max)+1
           if(dist[w]>max)
           max= dist[w] 
           
        }
    }
    return max
 }