Problema a portata di mano:
Ricerca di sottografi separati. Aggiorna sull'aggiunta o rimozione dei bordi.
Per prima cosa ho pensato di eseguire DFS dopo ogni operazione da entrambe le estremità del bordo, ma se tengo informazioni sui sottotitoli nei vertici, l'aggiunta del bordo è O (1); ti basta unire i sottografi di entrambe le estremità.
Ora, se volessi rimuovere il bordo, avrei comunque bisogno di DFS / BFS (O (E + V), credo) e vedere se c'è un altro percorso tra le estremità del bordo. Come trasferisco questa responsabilità dalla CPU alla RAM? Ne vale la pena?
Modifica: spiegazione del sistema
Basato su Circuitry dal gioco Factorio. Fondamentalmente ho oggetti con input e output. Ogni segno di spunta, se l'input è cambiato, l'output viene ricalcolato in base ai criteri all'interno dell'oggetto. Posso collegare input, output e pali (semplice vertice) con due tipi di cablaggio, ciascuno trattato separatamente, ma riassunto all'interno dell'input. Se collego più uscite con lo stesso cavo, l'intera rete (sottografo) trasferisce la somma di tutte le uscite. Inoltre, voglio compilare una configurazione di oggetti in blueprint, che è fondamentalmente un nuovo oggetto con input e conteggi di output personalizzati.
Tratto i tipi di cablaggio come 2 grafici separati e trovo 2 tipi di reti. La rete contiene i riferimenti a tutti gli output (o singoli output riassunti) e gli input. Fondamentalmente ho solo bisogno di dividere tutto in reti. Per rimuovere un cavo DFS / BFS probabilmente funzionerebbe bene, ma mi sono chiesto se esiste una soluzione basata sulla memoria.