Grafo aciclico

di il
2 risposte

Grafo aciclico

Salve, dovrei svolgere questo esercizio:

Ho scritto il grafo e la DFS, ma adesso non so come proseguire, qualche aiuto?

2 Risposte

  • Re: Grafo aciclico

    Cosa non sai fare in particolare? Non discutere di tutto l'esercizio (che non si riesce neanche a leggere bene) ma posta il codice che hai scritto e concentrati sul prossimo passo.
  • Re: Grafo aciclico

    Questo è il codice:
    #include <iostream>
    #include<string>
    #include <fstream>
    #include<string>
    #include<sstream>
    using namespace std;
    int W=0;
    int G=1;
    int B=2;
    template <class H>
    void ordina(H** k, int n)
    {
    	int x;
    	for(int i=0; i<n; i++)
    	{
    		x=i;
    		for(int j=i+1; j<n; j++)
    		{
    			if(*k[i]>*k[j])
    			{
    				x=j;
    			}
    		}
    		H t=*k[i];
    		*k[i]=*k[x];
    		*k[x]=t;
    	}
    }
    ifstream input("C:\\Users\\Darkman\\Downloads\\input.txt");
    ofstream out("C:\\Users\\Darkman\\Downloads\\output.txt");
    template <class H>
    class grafo
    {
    	private:
    		H** K;
    		int** mat;
    		int n,m,t;
    		int len;
    		int *d, *p, *f, *c, *r;
    		int root;
    	public:
    		grafo(int x)
    		{
    			d=new int[len];
    			p=new int[len];
    			f=new int[len];
    			c=new int[len];
    			r=new int[len];
    			n=m=0;
    			len=x;
    			mat=new int*[len];
    			K=new H*[len];
    			for(int i=0; i<len; i++)
    			{
    				mat[i]=new int[len];
    				K[i]=0;
    			}
    			for(int i=0; i<len; i++)
    			{
    				for(int j=0; j<len; j++)
    					mat[i][j]=0;
    			}
    		}
    		int cerca(H x)
    		{
    		//	cout<<x<<endl;
    			for(int i=0; i<n; i++)
    			{
    		//		cout<<*K[i]<<" ";
    				if(*K[i]==x)
    					return i;
    			}
    			return -1;
    		}
    		void aggiunginodo(H x)
    		{
    			if(cerca(x)>=0) return;
    			K[n]=new H(x);
    			n++;
    			ordina(K,n);
    		}
    		void aggiungiarco(H x, H y)
    		{
    			int i=cerca(x);
    			int j=cerca(y);
    		//	cout<<i<<" "<<j<<endl;
    			if(i<0 || j<0) return;
    			mat[i][j]=1;
    			m++;
    		}
    		void stampa()
    		{
    			for(int i=0; i<n; i++)
    			{
    				cout<<"("<<*K[i];
    				for(int j=0; j<n; j++)
    				{
    					if(mat[i][j]==1)
    						cout<<", "<<*K[j];
    				}
    				cout<<") ";
    			}
    		}
    		void DFS()
    		{
    			t=0;
    			for(int i=0; i<n; i++)
    			{
    				c[i]=W;
    				p[i]=-1;
    			}
    			for(int i=0; i<n; i++)
    			{
    				val=0;
    				if(c[i]==W)
    				{
    					root=i;
    					DFS_visit(i);
    				}
    				if(val>max)
    					max=val;	
    			}
    			cout<<max<<endl;
    		}
    		DFS_visit(int i, int& val)
    		{
    			c[i]=G;
    			d[i]=t++;
    			r[i]=root;
    			for(int j=0; j<n; j++)
    			{
    				if(mat[i][j]==1)
    				{
    					if(c[j]==W)
    					{
    						p[j]=i;
    						DFS_visit(j);
    					}
    				}
    					
    			}
    			c[i]=B;
    			f[i]=t++;
    		}
    };
    In output dovrei dare il numero di archi scoperti durante la Dfs, ma non ho idea di come si faccia, avevo provato mettendo una variabile che parte da 0 e incrementi quando trova un nodo dalla matrice di adiacenza e lo visita..ma l'output non risulta corretto
Devi accedere o registrarti per scrivere nel forum
2 risposte