componenti connesse

[CuriousCI]

Dato un grafo non diretto $G = (V, E)$ scrivere lo pseudocodice di un algoritmo che trova le componenti connesse del grafo in $O(|V| + |E|)$

• L'output è un array a di lunghezza $|V|$ in cui a[v] = i indica che il vertice v sta nell'i-esima componente connessa

[CuriousCI]

L'idea è quella che c'è un nodo immaginario $\alpha$ da cui è possibile raggiungere tutti gli altri, quindi rende possibile visitare tutte le componenti connesse del grafo. La complessità è la $O(2n + m) = O(n + m)$ dato che è la stessa di un dfs con aggiunto $\alpha$ (che ha grado $n$)

pub fn find_components(graph: &[Vec<usize>]) -> Vec<usize> {
    let mut components = vec![0; graph.len()];
    let mut component = 1;

    for x in 0..graph.len() {
        if components[x] == 0 {
            dfs_components(graph, x, &mut components, component);
            component += 1;
        }
    }

    components
}

fn dfs_components(graph: &[Vec<usize>], x: usize, components: &mut Vec<usize>, component: usize) {
    components[x] = component;

    for &y in &graph[x] {
        if components[y] == 0 {
            dfs_components(graph, y, components, component)
        }
    }
}

[Frisbon]

Idea molto smart devo ammettere

[LeoCosta02]

Comp(Graph G)
comp: int[n]=[0..0]
index=0
for each (x appartenente al grafo){
if (comp[x]==0){
index++

Dfs_rec_comp()

}
}

Dfs_rec_comp(Graph g , vert x , int[n] comp , int index)

comp[x]=index
for each y adiacente ad x{

 if(comp[y]==0)
  Dfs_rec_comp(G,y,comp,index)

}

[atyion]

Ciao a tutti. Ho fatto questo codice Python al volo. Ho un po' un dubbio per quel che concerne il costo computazionale.
Se non funziona su qualche testcase o se avete qualche domanda sul codice commentate pure.

def trova_componenti(graph):
    visit = set()
    res = []
    def dfs(x):
        visit.add(x)
        if x<len(graph):
            for i in graph[x]:
                if i not in visit:
                    res[-1].add(x)
                    res[-1].add(i)
                    dfs(i)


    for x in range(len(graph)):
        if x not in visit:
            res.append(set())
            dfs(x)
    return res


if __name__ == "__main__":
    graph = [[1], [2, 0], [3, 1, 4], [2], [2], [6], [5]]
    print(trova_componenti(graph))
    
  

[atyion]

nvm il costo computazionale ci sta secondo questo sito

[CuriousCI]

Attento! Stai usando un set(), che non ha operazioni proprio in $O(1)$ (cioè: sì ma no), specialmente quel not in visit... avevo dato dei suggerimenti a riguardo qui

[Warcophyr]

def dfs(graph, x, conect,cc, componet):

    conect[x] = cc
    componet.append(x)
    for y in graph[x]:
        if conect[y] == 0:
            componet = dfs(graph, y, conect,cc, componet)

    return componet


def found_conected(graph):
    conect = len(graph)*[0]
    output = []
    cc = 1
    for i in range(len(graph)):
        componet = []
        if conect[i] == 0: 
            output.append(dfs(graph, i, conect, cc, componet))
            cc+=1

    return output

[cornflexxx]

Itero su tutti i vertici $v\in V(G)$ e per ogni vertice se non è stato ancora visitato inizio una $DFS$ e aggiorno un contatore comp che tiene conto delle componenti trovate fin ora. La funzione DFS(G,v,vis,comp,a) è una normale $DFS$ che assegna ad ogni vertice $u$ trovato dalla $DFS$ la sua componente di appartenenza con $a[v] = comp$.

componenti_connesse(G):
    a := [0,...,0]
    vis := [0,...,0]
    comp = 1
    for v in V(G):
        if vis[v] == 0:
            DFS(G,v,vis,comp,a)
            comp += 1
    return a

[CarloDaRomadev]

def componenti_connesse(G)
	comp = [0,...,0]
	C = 0
	for v in V(G){
		if comp[v] == 0{
			assegna_componente(vis, comp, v, C++)
                }
	}
	return comp

def assegna_componente(vis, comp, v, C)
	comp[v] = C
	for w in v.adiacente(){
		assegna_componente(vis, comp, w, C)
	}