Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Algo(G,a,b,c)
- INIT(G)
- FOR EACH v in V do
- if(c[v]=bianco)then
- DFS_VISIT(G,v,c)
- if(DFS_VISIT(G,v,c)==a)then
- DFS_VISIT2(G,v,c)
- if(DFS_VISIT2(G,v,c)==c)then
- DFS_VISIT3(G,v,c)
- if(DFS_VISIT(G,v,c)==a && DFS_VISIT2(G,b,c)==b && DFS_VISIT3 == c) then
- DFS_CICLO(G,v,c)
- else
- return false // NON C'E' UN PERCORSO che attraversa a,b,c
- if(DFS_CICLO(G,v,c)==true)then //verifico se il percorso è infinito
- return true
- return false
- --------------------------
- DFS_VISIT(G,v,c)
- if(c[v]==a)then
- return v
- c[a]=grigio
- for each u in ADJ[a] do
- if (c[u]=bianco) then //controllo se l'adiacente è bianco
- if (u==a) then //se lo è verifico se è esattamente b
- return u //se lo è, lo ritorno
- else
- DFS_VISIT(G,u,c) //altrimenti,continuo a scorrere DFS_VISIT per l'adiacente
- c[a]=nero
- --------------------------
- DFS_VISIT2(G,v,c)
- if(c[v]==a)then
- return v
- c[b]=grigio
- for each x in adj[b] do
- if (c[x]=bianco) then
- if (x==b) then
- return x
- else
- DFS_VISIT2(G,x,c)
- c[b]=nero
- --------------------------
- DFS_VISIT3(G,v,c)
- if(c[v]==a)then
- return v
- c[c]=grigio
- for each y in adj[c] do
- if (c[c]=bianco) then
- if(c==c)then
- return x
- else
- DFS_VISIT3(G,y,c)
- c[y]=nero
- ----------------------------
- DFS_CICLO(G,c,c)
- c[c]=grigio
- for each ciclo in adj[c] do
- if (c[ciclo]=bianco) then
- DFS_CICLO(G,ciclo,c)
- else if(c[ciclo]=grigio)then
- return true
- c[ciclo]=nero
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement