parcours d'un grapphe en largeur

Version imprimable

27/08/2007, 13h44
onlytime

parcours d'un grapphe en largeur

bonjour a tous,
voila je cherche l'implementationen pascal de l'algorithme de parcours d'un graphe en largeur,ceci dis l'algorithme j'ai pu l'avoir,mais c'est juste que je suis tombée sur des algorithmes qui utilisent une file ,et dans ma structure de données je veux juste un tableau qui contient les somets de mon graphe est une liste qui contient les successeurs de chaque sommet
merci
27/08/2007, 13h57
Nemerle

et qu'est-ce qui te pose problème pour adapter ton algo??
27/08/2007, 14h13
onlytime

la structure de données je suis pas certaine que c'est la bonne

Parcours en largeur d'un graphe

Bonjour,
j'ai farfouillé dans mes archives datant de 2003, j'ai trouvé ça :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
procedure recherche_chemin;
var p,q:integer;
begin
if n=0 then writeln('Le graphe est vide...')
else
begin
write('entrer l''extrémité initiale du chemin:');readln(s1);
write('entrer l''extrémité finale du chemin:');readln(s2);
if est_present(s1) and est_present(s2) then
begin
if chemin_existe(s1,s2) then
begin
    p:=1;
    c1:=s2;
    chm[p]:=c1;
    while (c1<>s1) do
    begin
        p:=p+1;
        c1:=sommets[pred(c1)^.val];
        chm[p]:=c1;
    end;
    writeln('*****Voici le chemin recherch‚*****');
    for q:=p downto 1 do
    begin
        if q=1 then
        write(chm[q])
        else
        write(chm[q],'ÄÄ>');
    end;
end;
end;
if (not(est_present(s1)) or not(est_present(s2)))or(not(chemin_existe(s1,s2))) then
write('il n''‚xiste pas un chemin entre ',s1,' et ',s2);
end;
if n=0 then
begin
writeln;
write('appuyez sur une touche pour continuer...');
readkey;
end;
end;

Je sais que le code n'est pas indenté, peu clair, contient des anomalies, peut-être que ça marche pas, j'ai bien dit qu'il s'agissait d'un vieux programme, j'espère qu'il vous aidera.
Bon cour@ge.

ben merci bien pour votre qui est un peu trop ambigue ^^ mais j'ai pu faire un petit code avec l'aide d'un collégue

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
const nbsommet:=10;
 
type tableau:array[1..nbsommet] of boolean;
 
type ptr:^liste;
       liste=record
       val:integer;
       suiv:ptr;
       end;
 
type graphe:array[1..nbsommet]of ptr;
 
 
 procedure par(g:graphe);
 var p:ptr;i:integer;marquer:tableau;
 begin
    i:=0;for i:=0 to nbsommet do
      begin
      g[i]:=false;
      end;
    for i:=0 to nbsommet do
       begin
       if marquer[g[i]]:=false then {le sommet n'est pas marqué}
       write('g[i]');
       marquer[g[i]):=true;
       p:=g[i];      {parcourir la liste des successeurs}
       while (p<>nil) do
           begin
               if marque(g[i]^.val):=false then
               write('g[i]^.suiv');
              marquer[g[i ]^.suiv]:=true;
          end;
       end;
end;

Bonjour,
y a pas de quoi, voici un bonus :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
 
          (**************************************)
function chemin_existe(s1,s2:unsommet):boolean;
var aux,aux1:ref;var i:integer;
begin
        X1:=[s1];X2:=[s1];
        while (X1<>[]) and (not(accessible(s2))) do
        begin
            i:=1;
            while not(sommets[i] in X1) and (i<=n) do i:=i+1;
            c1:=sommets[i];
            X1:=X1-[c1];
            x:=index(c1);
            aux:=p[x];
            while (aux<>nil) do
            begin
                c2:=sommets[aux^.val];
                if not(accessible(c2)) then
                begin
                    X1:=X1+[c2];
                    X2:=X2+[c2];
                    y:=aux^.val;
                    aux1:=prd[y];
                    while(aux1^.val<>x) and (aux1<>nil) do aux1:=aux1^.suiv;
                    if aux1^.val=x then prds[y]:=aux1;
                end;
                aux:=aux^.suiv;
           end;
        end;
if accessible(s2) then
 chemin_existe:=true
else chemin_existe:=false;
end;
          (**************************************)
procedure recherche_chemin;
var p,q:integer;
begin
textcolor(7);
if n=0 then writeln('Le graphe est vide...')
else
begin
write('entrer l''‚xtr‚mit‚ initiale du chemin:');readln(s1);
write('entrer l''‚xtr‚mit‚ finale du chemin:');readln(s2);
if est_present(s1) and est_present(s2) then
begin
if chemin_existe(s1,s2) then
begin
    p:=1;
    c1:=s2;
    chm[p]:=c1;
    while (c1<>s1) do
    begin
        p:=p+1;
        c1:=sommets[pred(c1)^.val];
        chm[p]:=c1;
    end;
    writeln('*****Voici le chemin recherch‚*****');
    for q:=p downto 1 do
    begin
        if q=1 then
        write(chm[q])
        else
        write(chm[q],'ÄÄ>');
    end;
end;
end;
if (not(est_present(s1)) or not(est_present(s2)))or(not(chemin_existe(s1,s2))) then
write('il n''‚xiste pas un chemin entre ',s1,' et ',s2);
end;
if n=0 then
begin
writeln;
textcolor(29);
write('appuyez sur une touche pour continuer...');
readkey;
end;
end;
         (**************************************)

Bon cour@ge.