# VISITEDIGRAFI_1_SvoltiInAula

Jan 23rd, 2016
317
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. //VISTE DI GRAFI
2.
3. VERIFICA_ARCO(A,u,v) /* costo Theta(n) */
4.     trovato = false
5.     x = A[u]
6.     while (x != NULL)
7.         if x.info == v
8.             trovato = true
9.         x = x.next
10.     return trovato
11.
12. VERIFICA_NON_ORIENTATO(A,u,v) /* costo Theta(n^3) */
13.     for i=0 to A.length-1
14.         x = A[i]
15.         while x != NULL
16.             if (!VERIFICA_ARCO(A,x.info,i))
17.                 return false
18.             x = x.next
19.     return true
20.
21.
22. VERIFICA_UNIONE(A1,A2) /* costo Theta(n^3) */
23.     for i=0 to A1.length-1
24.         for j=0 to A1.length-1
25.             if(!(VERIFICA_ARCO(A1,i,j) OR VERIFICA_ARCO(A2,i,j)))
26.                 return false
27.     return true
28.
29. VERIFICA_UNIONE(A1,A2) /* costo Theta(n^2) */
30.     /* B è una matrice di interi con A1.length righe e A1.length colonne */
31.     for i=0 to A1.length-1
32.         for j=0 to A1.length-1
33.             B[i][j] = 0
34.
35.     for i=0 to A1.length-1
36.         x = A1[i]
37.         while x != NULL
38.             B[i][x.info] = 1
39.             x = x.next
40.
41.     for i=0 to A2.length-1
42.         x = A2[i]
43.         while x != NULL
44.             B[i][x.info] = 1
45.             x = x.next
46.
47.     for i=0 to A1.length-1
48.         for j=0 to A1.length-1
49.             if(B[i][j] == 0)
50.                 return false
51.
52.     return true
53.
54.
55. IS-CONNECTED(A)
56.     for i=0 to A.length-1
57.         color[i] = 0
58.
59.     q = EMPTY-QUEUE()
60.     color[0] = 1
61.     ENQUEUE(q,0)
62.
63.     while !IS-EMPTY(q)
64.         u = DEQUEUE(q)
65.         x = A[u]
66.         while x != NULL
67.             if(color[x.info] == 0)
68.                 color[x.info] = 1
69.                 ENQUEUE(q,x.info)
70.             x = x.next
71.         color[u] = 2
72.
73.     for i=0 to color.length-1
74.         if( color[i] == 0)
75.             return false
76.
77.     return true
78.
79.
80. DISTANZA(A,v)
81.     for i=0 to A.length-1
82.         color[i] = 0
83.         D[i] = 0
84.
85.     q = EMPTY-QUEUE()
86.     color[v] = 1
87.     EUQUEUE(q,v)
88.
89.     while !IS-EMPTY(q)
90.         u = DUQUEUE(q)
91.         x = A[u]
92.         while x != NULL
93.             if(color[x.info] == 0)
94.                 D[x.info] = D[u]+1
95.                 color[x.info] = 1
96.                 ENQUEUE(q,x.info)
97.             x = x.next
98.         color[u] = 2
99.
100.     return D
101.
102.
103. CONNESSO(A)
104.     for i=0 to color.length-1
105.                 /* color.length = A.length */
106.         color[i] = 0
107.     DFS(A,0,color)
108.     for i=0 color.length-1
109.         if color[i] == 0
110.             return FALSE
111.     return TRUE
112.
113. DFS(A,i,color)
114.     color[i] = 1
115.     x = A[i]
116.     while x != NULL
117.         if( color[x.info] == 0)
118.             DFS(A,x.info,color)
119.         x = x.next
120.     color[i] = 2
121.
122.
123. STESSA_COMPONENTE_FORTEMENTE_CONNESSA(A,u,v)
124.     for i=0 to color.length-1
125.         color[i] = 0
126.     DFS(A,u,color)
127.     if color[v] == 0
128.         return FALSE
129.
130.     for i=0 to color.length-1
131.         color[i] = 0
132.     DFS(A,v,color)
133.     if color[u] == 0
134.         return FALSE
135.
136.     return TRUE
137.
138. COMPONENTI_CONNESSE(A)
139.     for i=0 to color.length-1
140.         color[i]=0
141.
142.     cont = 0
143.     for i=0 to A.length-1
144.         if color[i] == 0
145.             cont++
146.             DFS(A,i,color)
147.     return cont
148.
149.
150. COMPONENTI_CONNESSE_CON_PROPRIETÀ_P(A)
151.     for i=0 to color.length-1
152.         color[i]=0
153.
154.     cont = 0
155.     for i=0 to A.length-1
156.         if color[i] == 0
157.             cont++
158.             DFS(A,i,color,cont)
159.     /*
160.     color[0] = 1
161.     color[1] = 2
162.     color[2] = 1
163.     color[3] = 3
164.     color[4] = 1
165.     ...
166.     */
167.
168.     for i=0 to cont /* per tutte le componenti connesse */
169.         nodi = 0
170.         for j=0 to color.length-1
171.             if color[j]==i
172.                 nodi++
173.         if nodi == 10 return TRUE
174.     return FALSE
175.
176.     /* ho controllato se esiste una componente connessa con 10 nodi */
177.
178.
179. DFS(A,i,color,cont)
180.     color[i] = cont
181.     x = A[i]
182.     while x != NULL
183.         if( color[x.info] == 0)
184.             DFS(A,x.info,color,cont)
185.         x = x.next
186.
187. /* ritorna un array che contiene per ogni nodo l'indice del nodo
188.    da cui provengo quando lo visito in una DFS */
189.
190. ALBERO_RICOPRENTE(A,u)
191.     for i=0 to A.length-1
192.         color[i] = 0
193.         parent[i] = -1
194.
195.     DFS_PARENT(A,u,color,parent)
196.     return parent
197.
198.
199. DFS_PARENT(A,u,color,parent)
200.     color[u] = 1
201.     x = A[u]
202.     while x != NULL
203.         if (color[x.info] == 0)
204.             parent[x.info] = u
205.             DFS_PARENT(A,x.info,color,parent)
206.         x = x.next
207.
208.
209. /* calcola un albero ricoprente (modifica della funzione sopra */
210.
211. ALBERO_RICOPRENTE_2(A,u)
212.     for i=0 to A.length-1
213.         color[i] = 0
214.         parent[i] = -1
215.
216.     DFS_PARENT(A,u,color,parent)
217.
218.     /* temp è un array di A.length posizioni che contiene riferimenti ai nodi dell'albero */
219.
220.     for i=0 to temp.length-1
221.         /* n = nuovo nodo dell'albero */
222.         temp[i] = n
223.         temp[i].info = i
224.         temp[i].parent = NULL
225.         temp[i].left = NULL
226.         temp[i].right = NULL
227.
228.     /* t è un nuovo albero di grado arbitrario */
229.     t.root = NULL
230.
231.     for i=0 to parent.length-1
232.         if(parent[i]== -1)
233.             t.root = temp[i]
234.         else
235.             temp[i].right = temp[parent[i]].left
236.             temp[parent[i]].left = temp[i]
237.             temp[i].parent = temp[parent[i]]
238.     return t
239.
240. /* ritorna un array contenente, per ogni nodo, l'ordine con cui è stato raggiunto
241.    in una DFS */
242.
243. DFS_ORDINE(A,v)
244.     for i=0 to A.length-1
245.         color[i]=0
246.         ordine[i]=-1
247.
248.     visitati = 0
249.     visitati = DFS_ORDINE2(A,v,color,
250.                            ordine,visitati)
251.     return ordine
252.
253. DFS_ORDINE2(A,v,color,ordine,visitati)
254.     visitati++
255.     ordine[v] = visitati
256.     color[v] = 1
257.     x = A[v]
258.     while x != NULL
259.         if color[x.info] == 0
260.             visitati = DFS_ORDINE2(A,x.info,color,ordine,visitati)
261.         x = x.next
262.     return visitati
RAW Paste Data