Ir ao conteúdo
  • Cadastre-se
Kevin De Bortoli

[Help-Me] Programa incompleto

Recommended Posts

Boa tarde pessoal, meu nome é Kevin sou estudante de Ciências da Computação na Facape, e estou com um problema no meu código de grafos. Gostaria de saber se alguém poderia me ajuda com meu probleminha.

 

O programa deve achar o número cromático de um grafo. No meu programa ele funciona com grafos que tenham seus vértices de forma seguida, mas quando trocamos a numeração deles ele fica dando número errado.

 

Aqui abaixo o meu programa.

Program NCromatico;uses crt, dos;varMAdjacencia : Array [1..100,1..100] of integer; {Matriz de Adjacencia do Grafo}n,m         : Integer;      {Quantidade de Vertices e de Arestas direcionadas do Grafo}arquivo     : Text;         {Arquivo texto onde esta o Grafo}arqok       : Boolean;      {Arquivo encontrado ou nao}nomearquivo : String;       {Nome do arquivo a ser utilizado}Auxarq      : Char;         {Auxiliar para colocar os dados do arquivo na matriz}Snumero     : String;       {Numero do arquivo em formato String}Inumero     : Integer;      {Numero do arquivo em formato inteiro}I, J        : Integer;      {Auxiliares para varrer a matriz}erro        : Integer;      {Erro na transformacao de String para Inteiro}Corvertice   : Array [1..100] of integer;adj        : Array [1..100] of integer;coradj  : Array [1..100] of integer;contadj : integer;cor            : integer;cont           : integer;numCromatico   : integer;resp           : string;label 23;beginrepeat                                                    textbackground(1);     clrscr;     arqok := false;     while not arqok do         {Verificando a existencia do arquivo}     begin          write('Digite o nome do arquivo: ');          readln (nomearquivo);          nomearquivo:=concat(nomearquivo,'.txt');          if Fsearch (nomearquivo,'') <> '' then          begin               arqok := true;               writeln('Arquivo localizado com sucesso!');               readkey;               clrscr;          end          else          begin               writeln ('Arquivo inexistente, tente novamente!')          end;     end;     for i := 1 to 100 do     for j := 1 to 100 do     MAdjacencia [i,j] := 0;     writeln('Trabalho dos alunos Adenner Barros, Clelio Italo e Kevin De Bortoli ');     writeln(' ');     writeln('Matriz de Adjacencia do Grafo no arquivo:');     writeln(' ');     assign (arquivo, nomearquivo);     reset (arquivo);     snumero := '';     i := 1;    {Preenchimento inicial na linha  1 }     j := 1;    {Preenchimento inicial na coluna 1 }     m := 0;     While not eof (arquivo) do     {Preenchimento da Matriz de Adjacencia do Grafo}     begin          read(arquivo, auxarq);          if (auxarq <> ' ') and (auxarq <> chr(13)) and (auxarq <> chr(10)) then          begin               snumero := concat (snumero,auxarq);          end          else          begin               val (snumero,inumero,erro);               if (erro <> 0) and (auxarq <> chr(10)) then               begin                    Writeln('Erro: ', erro, 'O Arquivo nao possui um digrafo'{'. Arquivo nao possui um grafo'});                    readkey;                    goto 23;               end;               snumero := '';               MAdjacencia [i,j] := inumero;               if inumero <> 0 then m := m + 1;{Definindo a quantidade de Arestas Dirigidas em digrafos}               if auxarq = ' ' then               begin                    write (MAdjacencia [i,j], ' ');                    j := j + 1;               end               else               begin                    if (auxarq <> chr(10)) then                    begin                         writeln (MAdjacencia [i,j], ' ');                         i := i + 1;                         j := 1;                    end;               end;          end;          {do if}     end;               {do while eof}          val (snumero,inumero,erro);          if (erro <> 0) and (auxarq <> chr(10)) then               begin                    Writeln('Erro: ', erro,'. Arquivo nao possui um grafo');                    readkey;                    halt;               end;          MAdjacencia [i,j] := inumero;     writeln (MAdjacencia [i,j], ' ');     m := m div 2; {descomente essa linha para grafos}     n := i;     writeln('');     writeln('');     writeln('n= ',n, ' e m= ', m);     close(arquivo);     readkey;              for i:=1 to 100 do begin           adj [i] := 0;           coradj [i] := 0;           corvertice [i] := 0;     end;                  if ((n = 1) and (m = 0)) then  //verifica se o grafo e trivial     begin        writeln('Este grafo e um grafo Trivial: Vertice 1 tem  a cor 1');                                           end     else     begin                              contadj := 0;               for i := 1 to n do                 begin                                   for j := 1 to n do //matriz para verificar vertices adjacentes                                                              if (MAdjacencia [i,j] <> 0) then                      begin                             adj[contadj + 1] := j;                                contadj := contadj + 1;                      end;                                                                             for j := 1 to contadj  do //Preenchendo as cores dos vertices adjancentes                        if (Corvertice[adj[j]] <> 0) then                           coradj[j] := Corvertice[adj[j]]                        else                           coradj[j] := 0;                                                  //Procura a cor para colocar no vertice)                    cor := 1;                    while (Corvertice[i] = 0) and (cor <= (contadj + 1)) do                    begin//Verificando cores dos adjacentes                        cont := 0;                        for j := 1 to contadj do                                                    if (cor <> coradj[j]) then                               cont := cont + 1;//Pintando. Se o cont for maior que os contadores passados, então o cont//passou por todos vertices adjacentes  e a cor nÑo foi usada                        if (cont >= contadj) then                        begin                             Corvertice[i] := cor;                             break;                        end; //if                        cor := cor + 1;                    end;//while                                   contadj := 0;               end; //for               writeln;               numCromatico := 0;               for i := 1 to n do               begin                    writeln ('Vertice ', i,' Cor ', Corvertice[i]);                    if (numCromatico < Corvertice[i]) then                        numCromatico := Corvertice[i]; //quantidade de cores               end;//for               writeln ('Numero Cromatico: ', numCromatico);     end;  //else23:     writeln ('Deseja testar outro grafo? <s/n>');     readln (resp);until (resp = 'n');end.   

Desde já Grato,

Kevin De Bortoli

 

A matriz pela qual meu programa erra:

 

0 0 0 1 0 0 0
0 0 1 0 1 1 0
0 1 0 1 0 0 0
1 0 1 0 1 0 0
0 1 0 1 0 0 0
0 1 0 0 0 0 0
0 0 0 0 0 0 0

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora





Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×