Skip to content

Esercizio per laboratorio di Algoritmi - 2017

Notifications You must be signed in to change notification settings

n3d1117/LabAlg17

Repository files navigation

Testo dell'esercizio

In questo esercizio si vuol analizzare l'algoritmo per trovare le componenti fortemente connesse in grafi diretti.

A tal fine si scrivano i seguenti programmi:

  1. un programma per la generazione di grafi causali con un numero di nodi a scelta ed una determinata probabilità di presenza di archi tra vertici (ad esempio il programma potrebbe partire da una matrice di adiacenza contenente tutti 0 e potrebbe proseguire scorrendo gli elementi della matrice cambiando ad 1 un arco con una certa probabilità)

  2. un programma per cercare le componenti fortemente connesse, implementando sia DFS che DFS-VISIT

  3. Un programma che permetta di condurre esperimenti su grafi casuali con dimensione crescente e con probabilità di presenza di archi crescente.

  4. Descrivere infine gli esperimenti condotti in una relazione, allegando alla stessa sia il file .pdf che il .tex e tutte le illustrazioni presenti nella relazione