diff options
| -rw-r--r-- | DFS.cpp | 39 | ||||
| -rw-r--r-- | Es 3.cpp | 109 | ||||
| -rw-r--r-- | Es5.cpp | 46 | ||||
| -rw-r--r-- | Es6.cpp | 38 | ||||
| -rw-r--r-- | es4.cpp | 67 | ||||
| -rw-r--r-- | main.cpp | 73 |
6 files changed, 372 insertions, 0 deletions
@@ -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;
+}
@@ -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;
+}
@@ -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;
+}
@@ -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;
+}
|