Advertisement
Davencode

Untitled

Jul 6th, 2021 (edited)
20
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.42 KB | None | 0 0
  1. Algo(G,a,b,c)
  2. INIT(G)
  3. FOR EACH v in V do
  4. if(c[v]=bianco)then
  5. DFS_VISIT(G,v,c)
  6. if(DFS_VISIT(G,v,c)==a)then
  7. DFS_VISIT2(G,v,c)
  8. if(DFS_VISIT2(G,v,c)==c)then
  9. DFS_VISIT3(G,v,c)
  10. if(DFS_VISIT(G,v,c)==a && DFS_VISIT2(G,b,c)==b && DFS_VISIT3 == c) then
  11. DFS_CICLO(G,v,c)
  12. else
  13. return false // NON C'E' UN PERCORSO che attraversa a,b,c
  14. if(DFS_CICLO(G,v,c)==true)then //verifico se il percorso è infinito
  15. return true
  16. return false
  17.  
  18. --------------------------
  19.  
  20. DFS_VISIT(G,v,c)
  21. if(c[v]==a)then
  22. return v
  23. c[a]=grigio
  24. for each u in ADJ[a] do
  25. if (c[u]=bianco) then //controllo se l'adiacente è bianco
  26. if (u==a) then //se lo è verifico se è esattamente b
  27. return u //se lo è, lo ritorno
  28. else
  29. DFS_VISIT(G,u,c) //altrimenti,continuo a scorrere DFS_VISIT per l'adiacente
  30. c[a]=nero
  31.  
  32. --------------------------
  33.  
  34. DFS_VISIT2(G,v,c)
  35. if(c[v]==a)then
  36. return v
  37. c[b]=grigio
  38. for each x in adj[b] do
  39. if (c[x]=bianco) then
  40. if (x==b) then
  41. return x
  42. else
  43. DFS_VISIT2(G,x,c)
  44. c[b]=nero
  45.  
  46. --------------------------
  47.  
  48. DFS_VISIT3(G,v,c)
  49. if(c[v]==a)then
  50. return v
  51. c[c]=grigio
  52. for each y in adj[c] do
  53. if (c[c]=bianco) then
  54. if(c==c)then
  55. return x
  56. else
  57. DFS_VISIT3(G,y,c)
  58. c[y]=nero
  59.  
  60. ----------------------------
  61.  
  62. DFS_CICLO(G,c,c)
  63. c[c]=grigio
  64. for each ciclo in adj[c] do
  65. if (c[ciclo]=bianco) then
  66. DFS_CICLO(G,ciclo,c)
  67. else if(c[ciclo]=grigio)then
  68. return true
  69. c[ciclo]=nero
  70.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement