lm-tecniche-di-programmazione/doc/exercises/directed_cycle.md

author	title	keywords	subject	papersize	lang
Raffaele Mignone	Caratterizzazione della complessità di un algoritmo per la ricerca di cicli orientati in un grafo	Complessità Grafo Ciclo	Caratterizzazione della complessità	a4	it-IT

Ricerca di cicli orientati

Traccia

Scrivere un programma per la ricerca di directed cycles in un grafo orientato.

Soluzione

Il problema può essere risolto prendendo come base la ricerca in profondità classica. Ad essa deve essere aggiunto un modo per tenere memoria dei nodi presenti sul percorso che si sta esplorando. Ciò può essere fatto tramite l'uso di un array così come si è fatto per tenere traccia dei nodi visitati¹.

private fun dfs(graph: UndirectedGraph, vertex: Int) {
  graphInfo[vertex].isVisited = true
  graphInfo[vertex].isOnPath = true

  graph.adjacentVertex(vertex)
    .forEach {
      when {
        hasCycle() -> return@forEach
        !graphInfo[it].isVisited -> exploreChild(graph, vertex, it)
        graphInfo[it].isOnStack -> cycle = makeCycle(vertex, it)
      }
    }

  graphInfo[vertex].isOnPath = false
}

Quando tra i vertici adiacenti a quello che si sta esplorando si trova un nodo già presente sul percorso vuol dire che è stato trovato un ciclo. La costruzione del ciclo viene mostrata nel @lst:makeCycle

private fun makeCycle(
  start: Int,
  end: Int
): MutableCollection<Int> {
  val cycle = Stack<Int>()

  var currentVertex = start

  while (currentVertex != end) {
    cycle.add(currentVertex)
    currentVertex = graphInfo[currentVertex].previously
  }

  cycle.add(end)
  cycle.add(start)

  return cycle
}

Infine la funzione exploreChild (@lst:exploreChild) semplicemente si occupa di settare il predecessore e di eseguire la ricerca in profondità sul nuovo vertice.

private fun exploreChild(
  graph: UndirectedGraph,
  parent: Int,
  child: Int
) {
  graphInfo[child].previously = parent
  dfs(graph, child)
}

Complessità

L'algoritmo per l'individuazione dei grafi mostrato precedentemente è sostanzialmente una versione modificata della ricerca in profondità e nel caso peggiore deve visitare tutti i nodi percorrendo tutti gli archi, per cui ha una complessità pari a E + V.

Source code

• DirectedCycle

---

1. Nel caso specifico si è utilizzata una data class che conserva le informazioni isVisited, isOnPath e previously. ↩︎