Algoritmo per determinare quali vertici/bordi disconnetterebbero il grafico non indirizzato se rimosso
-
04-11-2019 - |
Domanda
Qualcuno è a conoscenza di un algoritmo per determinare quali vertici/bordi disconnetterebbero un grafico non indirizzato se rimosso? Per tutti i vertici/bordi.
Naturalmente potrei eseguire un BFS per ogni vertice e per ogni bordo per testare se il grafico rimanente sarebbe collegato. Ma c'è qualcosa di più efficiente?
Alla fine vorrei disegnare uniformemente un vertice/bordo da quelli che non avrebbero scollegato il grafico, per creare simulazioni per il routing di fallimento in una rete di computer.
Nessuna soluzione corretta
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange