From eff9b7e3ac6f894e03d644bfba564909a260794c Mon Sep 17 00:00:00 2001
From: Santo Cariotti <sancn@live.com>
Date: Fri, 17 Mar 2017 21:00:23 +0100
Subject: Grafi

---
 DFS.cpp  |  39 +++++++++++++++++++++++
 Es 3.cpp | 109 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 Es5.cpp  |  46 +++++++++++++++++++++++++++
 Es6.cpp  |  38 ++++++++++++++++++++++
 es4.cpp  |  67 +++++++++++++++++++++++++++++++++++++++
 main.cpp |  73 ++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 372 insertions(+)
 create mode 100644 DFS.cpp
 create mode 100644 Es 3.cpp
 create mode 100644 Es5.cpp
 create mode 100644 Es6.cpp
 create mode 100644 es4.cpp
 create mode 100644 main.cpp

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;
+}
-- 
cgit v1.2.3-18-g5258