Pages: [1]   Go Down
Print
Author Topic: modificare dfs  (Read 1282 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« on: 07-06-2009, 14:44:35 »

qualcuno mi deve aiutare...non capisco come modificare la dfs per farle fare quello che dico io..ad es in questo esercizio
Quote
• Dato in input un file della seguente forma:
Autori
Mario Rossi
Giovanni Bianchi
Filippo Gialli



Coautori
Mario Rossi Giovanni Bianchi
Giovanni Bianchi Filippo Gialli
Mario Rossi Giovanni Bianchi
Mario Rossi Giovanni Bianchi
Giovanni Bianchi Filippo Gialli



• Le connessioni sono indirette.
• Leggere il file e creare il grafo corrispondente scegliendo la rappresentazione più opportuna.
Giustificare la scelta. Il grafo è pesato negli archi ed è connesso. Il peso corrisponde al numero di
volte che due autori compaiono assieme nell’elenco di coautori (es. l’arco (Mario Rossi, Giovanni
Bianchi) avrà peso 3).
• Dati in input tre autori. Scegliere uno dei tre autori e lanciare una visita DFS del grafo. Fermarsi
quando gli altri due autori sono stati visitati.
• L’implementazione deve contenere la classe grafo con tutti gli attributi, metodi (o classi) necessari
al corretto funzionamento. Si gestiscano opportunamente le eccezioni. I metodi devono essere
commentati. E’ necessario implementare il metodo main
come si fa??ci provo in tutti i modi ma non funziona..
Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
TheSpecialOne
Apprendista Forumista
**
Offline Offline

Posts: 232



« Reply #1 on: 07-06-2009, 14:52:40 »

mi accodo...
Logged
djjeck
Matricola
*
Offline Offline

Gender: Male
Posts: 89


Ho una donna nuda per avatar. Non c'era di meglio.


WWW
« Reply #2 on: 07-06-2009, 15:48:06 »

Puoi aggiungere un parametro, al metodo ricorsivo, che rappresenti gli autori che devono ancora essere trovati.
Può ad esempio essere un array di String.
Il caso che arresta la ricorsione sarebbe quando l'array è vuoto.

Code:
dfs(nodo n, string[] autori_da_trovare) {
  if(n != white OR autori_da_trovare.length == 0)
    return autori_da_trovare

  n = gray

  //controllare se uno degli autori mancanti è stato trovato
  if(autori_da_trovare contiene n.autore)
    autori_da_trovare = autori_da_trovare - n.autore

  per ogni discendente {
    autori_da_trovare = dfs(discendente, autori_da_trovare)
  }
  n = black
  return autori_da_trovare
}
mancano alcuni accorgimenti per far arrestare la dfs al momento esatto, ma l'idea è questa
Logged
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« Reply #3 on: 07-06-2009, 17:21:43 »

Ho creato una mia impelementazione con la matrice di Adiacenza , qualcuno mi può dire se va bene? O cosa manca per essere migliorato?


Code:
public void Cammino(NodoGrafo x, String[] T)
  {
  if(T[0] == null)
  {
  System.out.println("Cammino arrestato");
  }
  else
  {
  st[x.indice(g.getNodi())] = Stato.APERTO;
 
 
 
      for(int i = 0; i < g.matrice.length ; i++)
      {
      if(g.matrice[g.getIndice(x)][i].getOrigine() == g.matrice[g.getIndice(x)][i].getDestinazione() )
      {
     i++;
      }
      Arco adj = g.matrice[g.getIndice(x)][i];
 
      int k = (adj.getDestinazione()).indice(g.getNodi());
 
 
      if(st[k] == Stato.INESPLORATO)
      {
     prev[k] = x;
     
     String [] F = new String[1];
     
      int y=0;
     
      for(int j = 0;j < T.length;j++)
      {
        if(!(adj.getDestinazione().getInfo()).equals(T[j]))
        {
        F[y] = T[j];
        y++;
        }
      }
         
       
     Cammino(adj.getDestinazione(),F);
      }
      }
 
      st[x.indice(g.getNodi())] = Stato.CHIUSO;
  }


EDIT:Ho fatto una piccola modifica...
« Last Edit: 07-06-2009, 17:40:45 by Alex_47 » Logged
poty
Matricola
*
Offline Offline

Posts: 95


« Reply #4 on: 17-06-2009, 11:48:49 »

io ho fatto cosi:

devi prima fare il random dei tre autori ed eseguire una visita DFS a partire dall'autore scelto.

poi ti crei un'ogetto autore come info gli metti uno string del nome boolean.

nella dfs ti crei 2 ogetti di tipo autore con il boolean false e il nome dei 2 autori per ogni istanza dell'ogetto autore.

ogni volta che controlla la dfs l'adiacenza, gli fai controllare se il nodo visitato la sua info è di uno dei due autori se lo è, imposti l'autore trovato a true

quando troverà entrambi gli autori avrai una lista di adiacenza normale, e i due ogetti entrambi true quindi ti basterà controllare che i due ogetti del metodo/classe DFS siano entrambi true, se lo sono quela determinata visita a partire da quel autore atraversa gli altri 2 autori.

PS io la DFS la faccio come classe...mi viene piu comodo lavorarci...non so voi
Logged
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« Reply #5 on: 17-06-2009, 12:02:14 »

eh?non ti puoi spiegare meglio?cmq la dfs è una classe come la dovresti fare?
Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
poty
Matricola
*
Offline Offline

Posts: 95


« Reply #6 on: 17-06-2009, 12:47:32 »

io ho fatto cosi:

devi prima fare il random dei tre autori ed eseguire una visita DFS a partire dall'autore scelto.

qui cosa c'è da capire? penso sai fare un random

poi ti crei un'ogetto autore come info gli metti uno string del nome boolean.

non penso ci sia di bisogno di dirti cosa sia un'ogetto...con 2 parametri string nome e boolean found


nella dfs ti crei 2 ogetti di tipo autore con il boolean false e il nome dei 2 autori per ogni istanza dell'ogetto autore.

dentro la dfs ti crei 2 istanze di tipo autore...non si capisce?

ogni volta che la dfs controlla l'adiacenza, gli fai controllare se il nodo visitato la sua info è di uno dei due autori se lo è, imposti l'autore trovato a true

adnon posso spiegartelo piu semplice di cosi...lo riscriverei uguale...

quando troverà entrambi gli autori avrai una lista di adiacenza normale, e i due ogetti entrambi true quindi ti basterà controllare che i due ogetti del metodo/classe DFS siano entrambi true, se lo sono quela determinata visita a partire da quel autore atraversa gli altri 2 autori.

dalla dfs che cosa ottieni? una lista della visita. dentro la classe dfs avrai pure i 2 oggetti di tipo autore con il boolean found se sono entrambi true allora quella visita passa per i 2 autori...piu chiaro di cosi...

PS io la DFS la faccio come classe...mi viene piu comodo lavorarci...non so voi

una dfs può essere fatta come metodo del grafo...che "logicamente" ha piu senso visto che è una visita del grafo come il preorder per un albero...ma come classe per far tutto quello che dobiamo fare è indispensabile per lavorarci piu facilmente...

non so come spiegartelo meglio....prendi spunto e poi sbattici la testa testate  yoh

Logged
Pages: [1]   Go Up
Print
Jump to: