Grafi

6 files changed, 372 insertions, 0 deletions

diff --git a/DFS.cpp b/DFS.cpp
new file mode 100644
index 0000000..fda5a33
--- /dev/null
+++ b/DFS.cpp
@@ -0,0 +1,39 @@
+#include <iostream>

+#define BIANCO 0  //Non Visitato

+#define NERO 2   //Visitato

+#define GRIGIO 1 //Non Finito

+#define INF 999999

+#include <vector>

+#include <fstream>

+#include <queue>

+#define MAXN 9999

+#define INDEF -1

+#include <stack>

+using namespace std;

+int V=9;

+int matriceAdj[MAXN][MAXN];

+ int colore[MAXN];

+ //DFS Tramite matrice di adiacenza

+ void dfsVisit (int u)

+ {

+ 	colore[u]= GRIGIO;

+ 	for (int i=0;i<V;i++)

+ 	{

+ 		if (matriceAdj[u][i] == 1 && colore[i] == BIANCO )

+ 		dfsVisit(i);

+ 	}

+ 	colore[u]= NERO;

+ }

+ // Le chiamate ricorsive sono quanti sono i nodi GRIGI

+ int dfs()

+ {

+ 	for (int i=0;i<V;i++) colore[i]=BIANCO;

+ 	for (int i=0;i<V;i++) if (colore[i]==BIANCO) dfsVisit(i);

+ }

+ 

+int main(int argc, char** argv) {

+	

+	//Vanno settati i dati riguardanti gli archi esistenti

+

+	return 0;

+}

diff --git a/Es 3.cpp b/Es 3.cpp
new file mode 100644
index 0000000..d525f62
--- /dev/null
+++ b/Es 3.cpp
@@ -0,0 +1,109 @@
+#include <iostream>

+#define BIANCO 0  //Non Visitato

+#define NERO 2   //Visitato

+#define GRIGIO 1 //Non Finito

+#define INF 999999

+#include <vector>

+#include <fstream>

+#include <queue>

+#define MAXN 9999

+#define INDEF -1

+#include <stack>

+using namespace std;

+typedef pair <int,int> p;

+std::priority_queue<p, std::vector<p>, std::greater<p> > Q;

+int V,E;

+int matriceAdj[MAXN][MAXN];

+int T;

+struct nodo {

+	vector <int> adj;

+	int inizio,fine;

+}no[MAXN];

+ int colore[MAXN];

+ bool Ciclico=false;

+ bool dfsVisit (int u)

+ {

+ 	cout<<u<<endl;

+ 	colore[u]= GRIGIO;

+ 	int inizio=++T;

+ 	no[u].inizio=inizio;

+ 	int a;

+ 	for (int i=0;i<no[u].adj.size();i++)

+ 	{

+ 		a=no[u].adj[i];

+ 		if (colore[a]==GRIGIO) 

+		 {

+		 	Ciclico=true;

+		 	return 1;

+		 }

+ 		if ( colore[a] == BIANCO )

+ 		{

+ 			int b=dfsVisit(a);

+ 			if (b)

+ 			{

+ 				return 1;

+ 			}

+ 		}

+ 	}

+ 	colore[u]= NERO;

+ 	int fine=++T;

+ 	no[u].fine=fine;

+ 	Q.push(p(fine,inizio));

+ 	return 0;

+ }

+ 

+  void dfsVisit2 (int u)

+ {

+ 	cout<<u<<endl;

+ 	colore[u]= GRIGIO;

+ 	int a;

+ 	for (int i=0;i<no[u].adj.size();i++)

+ 	{

+ 		a=no[u].adj[i];

+ 		if ( colore[a] == BIANCO )

+ 		dfsVisit(a);

+ 	}

+ 	colore[u]= NERO;

+ }

+ // Le chiamate ricorsive sono quanti sono i nodi GRIGI

+ void dfs()

+ {

+ 	for (int i=0;i<V;i++) colore[i]=BIANCO;

+ 	for (int i=0;i<V;i++) if (colore[i]==BIANCO)  if (dfsVisit(i)) return;

+ }

+ 

+ 

+int main(int argc, char** argv) {

+	ifstream in ("input.txt");

+	ofstream out ("output.txt");

+	in>>V>>E;

+	int a,b;

+	for (int i=0;i<E;i++)

+	{

+		in>>a>>b;

+		no[a].adj.push_back(b);

+	}

+	dfs();

+	for (int i=0;i<V;i++)

+	{

+		cout<<"nodo "<<i<<endl;

+		cout<<"Inizio "<<no[i].inizio<<"   Fine "<<no[i].fine<<endl;

+	}

+	if (!Ciclico)

+	{

+	for (int i=0;i<V;i++) colore[i]=BIANCO;

+	b=0;

+	while (!Q.empty())

+	{

+		a=Q.top().first;

+		Q.pop();

+		if (colore[a]==BIANCO) 

+		{

+			dfsVisit2(a);

+			b++;

+		}

+	}

+	cout<<"Il numero di Componenti connesse e' "<<b;

+    }

+	return 0;

+}

diff --git a/Es5.cpp b/Es5.cpp
new file mode 100644
index 0000000..8f6fb48
--- /dev/null
+++ b/Es5.cpp
@@ -0,0 +1,46 @@
+#include <iostream>

+#define BIANCO 0  //Non Visitato

+#define NERO 2   //Visitato

+#define GRIGIO 1 //Non Finito

+#define INF 999999

+#include <vector>

+#include <fstream>

+#include <queue>

+#define MAXN 9999

+#define INDEF -1

+#include <stack>

+using namespace std;

+typedef pair <int,int> p;

+struct nodo{

+	vector<int> adj;

+	vector<int> p;

+};

+

+int main(int argc, char** argv) {

+	int v,e;

+	int sorgente;

+	nodo no[v];

+	

+	priority_queue<p> Q;

+	int peso[v];

+	Q.push(p(0,sorgente));

+	

+	while(!Q.empty())

+	{

+		pair <int,int> a=Q.top();

+		Q.pop();

+		if (a.first > peso[a.second])

+		continue;

+		

+		for (int i=0;i<no[a.second].adj.size();i++)

+		{

+			if (peso[no[a.second].adj[i]]>a.first+ no[a.second].p[i])

+			{

+				peso[no[a.second].adj[i]]=a.first + no[a.second].p[i];

+				Q.push(p(peso[no[a.second].adj[i]],no[a.second].adj[i]));

+			}

+		}

+		

+	}

+	return 0;

+}

diff --git a/Es6.cpp b/Es6.cpp
new file mode 100644
index 0000000..9907eb9
--- /dev/null
+++ b/Es6.cpp
@@ -0,0 +1,38 @@
+#include <iostream>

+#include <algorithm>

+using namespace std;

+/* run this program using the console pauser or add your own getch, system("pause") or input loop */

+

+int main(int argc, char** argv) {

+	int v=5;

+	int matrice[v][v];

+	for (int i=0;i<v;i++)

+	{

+		for (int j=0;j<v;j++)

+		matrice[i][j]=9999;

+	}

+	for (int i=1;i<v;i++) matrice[i][i]=0;

+	matrice[1][4]=5;

+	matrice[1][2]=1;

+	matrice[2][3]=2;

+	matrice[3][1]=2;

+	matrice[3][4]=1;

+	matrice[4][1]=3;

+	for (int h=1;h<v;h++)

+	{

+		for (int i=1;i<v;i++)

+		{

+			for (int j=1;j<v;j++)

+			{

+				matrice[i][j]=min(matrice[i][j],matrice[i][h]+matrice[h][j]);

+			}

+		}

+	}

+	for (int i=1;i<v;i++)

+	{

+		for (int j=1;j<v;j++)

+		cout<<matrice[i][j]<<"  ";

+		cout<<endl;

+	}

+	return 0;

+}

diff --git a/es4.cpp b/es4.cpp
new file mode 100644
index 0000000..a1f1716
--- /dev/null
+++ b/es4.cpp
@@ -0,0 +1,67 @@
+#include <iostream>

+#define BIANCO 0  //Non Visitato

+#define NERO 2   //Visitato

+#define GRIGIO 1 //Non Finito

+#define INF 999999

+#include <vector>

+#include <fstream>

+#include <queue>

+#define MAXN 9999

+#define INDEF -1

+#include <stack>

+using namespace std;

+typedef pair<int,int> p;

+int V,E;

+

+struct nodo {

+	vector <p> adj;

+	int dist;

+	nodo(){

+		dist=INF;

+	}

+}no[MAXN];

+ int colore[MAXN];

+ void relax (nodo no[], int u, int z)

+ {

+ 	p v= no[u].adj[z];

+ 	if (no[v.first].dist> no[u].dist + v.second )

+ 	 {

+ 	 	no[v.first].dist= no[u].dist + v.second;

+ 	 }

+ }

+ 

+ void bf (nodo no[],int n, int s)

+ {

+ 	int i,j,z;

+ 	no[0].dist=0;

+ 	for (i=0;i<V;i++)  //Scorro 

+ 	{

+ 		for (j=0;j<V;j++)

+ 		{

+ 			for (z=0;z<no[j].adj.size();z++)

+ 			{

+ 				relax(no,j,z); 

+ 			}

+ 		}

+ 	}

+

+ }

+ 

+ 

+int main(int argc, char** argv) {

+	ifstream in ("input.txt");

+	ofstream out ("output.txt");

+	in>>V>>E;

+	int a,b,c;

+	for (int i=0;i<E;i++)

+	{

+		in>>a>>b>>c;

+		no[a].adj.push_back(p(b,c));

+	}

+	bf(no,V,0);  //Adiacenze, numeri di vertici, sorgente

+	for (int i=0;i<V;i++)

+	{

+		cout<<no[i].dist<<endl;

+	}

+	return 0;

+}

diff --git a/main.cpp b/main.cpp
new file mode 100644
index 0000000..911d7e6
--- /dev/null
+++ b/main.cpp
@@ -0,0 +1,73 @@
+#include <iostream>

+#define BIANCO 0  //Non Visitato

+#define NERO 1   //Visitato

+#define GRIGIO //Non Finito

+#define INF 999999

+#include <vector>

+#include <fstream>

+#include <queue>

+#define MAXN 9999

+#define INDEF -1

+#include <stack>

+using namespace std;

+int V=9;  //Nodi

+int precedente[MAXN];  //Vettore su cui viene salvato il percorso per arrivare alla destinazione

+struct nodo {

+	vector <int> adj;

+}no[MAXN];;

+ 

+ int bfsVisit (int s)

+ {

+ 		int dist[V];

+	int colore[V];

+	queue <int> q;

+	

+	for (int i=0;i<V;i++)

+	{

+		precedente[i]=-1;

+		dist[i]=INF;

+		colore[i]=BIANCO;

+	}

+	dist[s]=INF;

+	colore[s]=NERO;

+	q.push(s);

+	while (!q.empty())

+	{

+		int a=q.front();

+		q.pop();

+		for (int i=0;i<no[a].adj.size();i++)

+		{

+			int b=no[a].adj[i];

+			if (colore[b] == BIANCO)

+			{

+				q.push(b);

+				colore[b]=NERO;

+				precedente[b]=a;

+				dist[b]=dist[a] +1;

+			}

+		}

+	}

+	/*

+	stack <int> sta;

+	int i=3; // arrivo

+	sta.push(i);

+	while (precedente[i]!=INDEF)

+	{

+		

+	}

+	*/ //Procedura iterativa per stampare il percorso fino al nodo sorgente

+	

+ }

+ 

+ void stampaPercorso (int j)  //Procedura ricorsiva j=precedente[destinazione]

+ {

+ 	if (precedente[j] != INDEF )

+ 	stampaPercorso(precedente[j]);

+ 	cout<<j;

+ }

+int main(int argc, char** argv) {

+	

+	

+

+	return 0;

+}