// ***********************************************************
// Structure de donnees II : la file First In First Out (FIFO)
// (parfois appellee 'queue', comme au guichet de la banque)
//************************************************************
funcprot(0)

function S = coda()
    S = list()         // on utilise encore la liste de Scilab
endfunction
 
function Bool = videcoda?(S)
    Bool = (length(S)==0)
endfunction
 
function S = enqueue(S,el)  // Insertion
   S($+1) = el              // $ indique la queue de la liste
endfunction
 
function S = dequeue(S)      // deletion
   S(1) = null()
endfunction
 
function el = head(S)
    el = S(1)
endfunction
 
//----------------------------------------------------------------------- 
// Algorithme de parcours en largeur (BFS = breadth First Search)
// d'un graphe representé par une list d'adjacence 
// couleurs: 0=blanc, 1=gris, 2=noir
// dist: -1 pour l'infini
// pere: 0 pour NIL
//
// A partir d'un sommet s, on liste d'abord les voisins de s pour ensuite les explorer un par un.
// Ce mode de fonctionnement utilise donc une file dans laquelle on prend le premier sommet et 
// place en dernier ses voisins non encore explores.
// On utilise les fonctions de la file precedente
//-----------------------------------------------------------------------

function [coul,dist,pere] = BFS(E,s)
    coul = zeros(1,length(E))        // on fabrique une matrice de taille (1 x longueur de E)
    pere  = zeros(1,length(E))       // idem
    for(i = 1 : length(E))           // pour i variant de 1 -> 8 (= length(E1))
        dist(1,i) = -1               // le vecteur d est initialise a -1
    end
    
    coul(1,s) = 1
    dist(1,s)   = 0
    Q        = coda()                // Q est une file
    Q        = enqueue(Q,s)          //
    
while (~ videcoda?(Q))  
    u = head(Q)           // on pointe sur le tete de liste 
    for v = E(u)
        if (coul(v) == 0)  // test d'egalite a 0
            dist(v)   = dist(u)+1
            coul(v) = 1
            pere(v)  = u
            Q      = enqueue(Q,v)  
        end
    end
    
    coul(u) = 2
    Q = dequeue(Q)
end
endfunction

// la liste d'adjacence : une liste composee de 8 listes
// tracer au brouillon ce graphe
E1=list(list(2,3), list(), list(4,6), list(5), list(), list(7,5), list(), list(4,5))

// Appel à BFS
[coul,dist,pere]=BFS(E1,3)

// ---------------------------------THE END-------------------------