Binary Road
Gostaria de reagir a esta mensagem? Crie uma conta em poucos cliques ou inicie sessão para continuar.

Trabalho sobre Grafo

Ir para baixo

Trabalho sobre Grafo Empty Trabalho sobre Grafo

Mensagem  Renancr Dom 21 Nov 2010 - 18:40

GRAFO


Em matemática e ciência da computação, grafo é o objeto básico de estudo da teoria dos grafos. Tipicamente, um grafo é representado como um conjunto de pontos (vértices) ligados por retas (as arestas). Dependendo da aplicação, as arestas podem ser direcionadas, e são representadas por "setas".

Os grafos são muito úteis na representação de problemas da vida real, em vários campos profissionais. Por exemplo, pode-se representar um mapa de estradas através dos grafos e usar algoritmos específicos para determinar o caminho mais curto entre dois pontos, ou o caminho mais económico. Assim, os grafos podem possuir também pesos (ou custo), quer nas arestas quer nos vértices, e o custo total em estudo será calculado a partir destes pesos.

Grafos podem ser utilizados também em redes PERT no âmbito do planejamento de projetos. Neste caso, a cada aresta está associado o custo de execução, e as tarefas precedentes de uma outra serão suas afluentes.

Outro exemplo é o caso das redes de computadores, sendo cada terminal representado por um vértice, o cabo de rede pelas arestas e o custo associado a latência, por exemplo, ou o número de máquinas que a comunicação atravessa entre os nós. É nestes princípios que assenta todo o protocolo IP que torna possível a Internet ser uma realidade.

Grafos têm sido utilizados para representar o formalismo das redes complexas, onde o número de nós e de conexões entre esses nós é muito alto e complexamente estabelecido.

Introndução:

Uma possível definição para grafos: "O grafo propriamente dito é uma representação gráfica das relações existentes entre elementos de dados. Ele pode ser descrito num espaço euclidiano de n dimensões como sendo um conjunto V de vértices e um conjunto A de curvas contínuas (arestas)". Podemos avaliar um grafo através de seu tipo, propriedades e aplicações.

Busca em grafo:

Vários problemas representados por um grafo podem ser resolvidos efetuando uma busca nesse grafo. A busca em grafo consiste em explorar um grafo, de forma que obtenha um processo sistemático de como caminhar por seus vértices e arestas. Às vezes é preciso visitar todos os vértices de um grafos, as vezes o problema pode ser resolvido visitando somente um subconjunto dos vértices.
Se o grafo é uma árvore, esta questão se torna simples, podem utilizar as visitas em pré-ordem, ou ordem de nível.

Algoritmos de percurso:

Existem dois métodos de percurso em grafos: percurso em profundidade (depth-first search — DFS) e o percurso em largura (breadth first search — BFS).
A idéia básica do DFS é buscar "mais a fundo" no grafo quando possível. Assim, a partir de um vértice v, as arestas ainda não exploradas o são e, ao final, a busca retrocede.
A idéia do BFS é bastante simples: os vértices do grafo são visitados nível a nível, ou seja, todos os vértices a uma distância k do vértice inicial são visitados antes de qualquer vértice a uma distância k +1 do inicial.

Fonte: Wikipédia

Faça um programa para representar um grafo de 6 vertices, com arestas determinada pelo usuário, representar em uma matriz 6X6.

1- Faça o calculo do vértice com maior grau, e mostrar para o usuário o(s) vértice(s) com o maior grau.
2- Faça o calculo da soma dos graus de todos os 6 vértices.
3- Imprima um possivel caminho Hamiltoniano.


EM TESTE

Código:
#include <iostream>
using namespace std;

const int tam=6;
const int tam2=2*tam;

int makegrafo(int matriz[tam][tam], int aresta[tam2]);
void mgdv(int matriz[tam][tam]);
void stgv(int matriz[tam][tam]);
void hamilton(int aresta[tam]);

void main()
{
   int matriz[tam][tam], aresta[tam2], op, made=0;

   do{
      do{
         system("cls");
         cout<< "==================================================================\n";
         cout<< "\t1- Criar Grafo\n";
         cout<< "\t2- Encontrar a vertice com maior grau\n";
         cout<< "\t3- Somar todos os graus dos vertices\n";
         cout<< "\t4- Encontar um possivel caminho Hamiltoniano\n";
         cout<< "\t5- Sair\n";
         cout<< "==================================================================\n";
         cout<< "\n\tDigite a opcao desejada\n\t";
         cin>> op;
         if(op < 1 || op > 5)
         {
            system("cls");
            cout<< "\n\n\tOpcao invalida\n\n\n";
            system("pause");
         }
      }while(op < 1 || op > 5);
      if(op == 1)
      {
         made=makegrafo(matriz, aresta);
      }
      else
         if(op == 2)
         {
            if(made == 1)
               mgdv(matriz);
            else
            {
               system("cls");
               cout<< "\n\n\n\tNem um GRAFO foi criado ainda.\n\n\n";
               system("pause");
            }
         }
         else
            if(op == 3)
            {
               if(made == 1)
                  stgv(matriz);
               else
               {
                  system("cls");
                  cout<< "\n\n\n\tNem um GRAFO foi criado ainda.\n\n\n";
                  system("pause");
               }
            }
            else
               if(op == 4)
               {
                  if(made == 1)
                     hamilton(aresta);
                  else
                  {
                     system("cls");
                     cout<< "\n\n\n\tNem um GRAFO foi criado ainda.\n\n\n";
                     system("pause");
                  }
               }
   }while(op != 5);
}

int makegrafo(int matriz[tam][tam], int aresta[tam2])
{
   int vert, arest, l, c, cont=1, i, found;
   for(l=0; l<tam; l++)
      for(c=0; c<tam; c++)
         matriz[l][c]=0;
   for(l=0; l < tam2; l++)
   {
      do{
         system("cls");
         found=0;
         if(l > 0)
         {
            cout<< "Aresta = { ";
            for(c=0; c<l; c++)
            {
               if(c % 2 != 0)
               {
                  cout<< aresta[c] << "} ";
               }
               else
               {
                  cout<< "{" << aresta[c] << ",";
               }
            }
            cout<< " }";
         }
         cout<< "\n\nDigite um conjunto par de numeros de 1 ate 6 nao repetindo os pares\n\n";
         if(l % 2 == 0)
         {
            do{
               cout<< "\n\tDigite o primeiro numero do conjunto\n\t";
               cin>> aresta[l];
               if(aresta[l] < 1 || aresta[l] > 6)
               {
                  system("cls");
                  cout<< "\n\n\n\nO valor digitado nao poder ser menor do que 1 e maior do que 6\n\n\n";
                  system("pause");
                  system("cls");
                  if(l > 0)
                  {
                     cout<< "Aresta = { ";
                     for(c=0; c<l; c++)
                     {
                        if(c % 2 != 0)
                        {
                           cout<< aresta[c] << "} ";
                        }
                        else
                        {
                           cout<< "{" << aresta[c] << ",";
                        }
                     }
                     cout<< " }";
                  }
               }
            }while(aresta[l] < 1 || aresta[l] > 6);
         }
         else
         {
            do{
               cout<< "\n\tDigite o segundo numero do conjunto\n\t";
               cin>> aresta[l];
               if((aresta[l] < 1 || aresta[l] > 6) || (aresta[l] == aresta[l-1]))
               {
                  system("cls");
                  cout<< "\n\n\n\nO valor digitado nao poder ser menor do que 1 e maior do que 6, e nem repetido.\n\n\n";
                  system("pause");
                  system("cls");
                  if(l > 0)
                  {
                     cout<< "Aresta = { ";
                     for(c=0; c<l; c++)
                     {
                        if(c % 2 != 0)
                        {
                           cout<< aresta[c] << "} ";
                        }
                        else
                        {
                           cout<< "{" << aresta[c] << ",";
                        }
                     }
                     cout<< " }";
                  }
               }
            }while((aresta[l] < 1 || aresta[l] > 6) || (aresta[l] == aresta[l-1]));
            i=1;
            while(i < cont && found == 0)
            {
               if((aresta[i-1] == aresta[l-1] && aresta[i] == aresta[l]) || (aresta[i-1] == aresta[l] && aresta[i] == aresta[l-1]))
                  found=1;
               i+=2;
            }
         }
         if((found == 0) && (l % 2 != 0))
            cont+=2;
         else
            if((found == 1) && (l % 2 != 0))
            {
               system("cls");
               cout<< "O conjunto {" << aresta[l-1] << ", " << aresta[l] << "} ja existe, digite um diferente.\n\n";
               l--;
               system("pause");
            }
      }while(found == 1);
   }
   /*system("cls");
   cout<< "Aresta = { ";
   for(c=0; c<tam2; c++)
   {
      if(c % 2 != 0)
      {
         cout<< aresta[c] << "} ";
      }
      else
      {
         cout<< "{" << aresta[c] << ",";
      }
   }
   cout<< " }";
   cout<< "\n\n\n";
   for(l=0; l<tam; l++)
   {
      for(c=0; c<tam; c++)
         cout<< matriz[l][c] << " ";
      cout<< "\n";
   }*/
   for(vert=0; vert<tam; vert++)
   {
      for(arest=0; arest<tam; arest++)
      {
         for(l=1; l < tam2; l+=2)
            if(vert+1 == aresta[l-1] && arest+1 == aresta[l])
               matriz[vert][arest]= 1;
      }
   }
   /*cout<< "\n\n\n";
   for(l=0; l<tam; l++)
   {
      for(c=0; c<tam; c++)
         cout<< matriz[l][c] << " ";
      cout<< "\n";
   }
   system("pause");*/
   return 1;
}

void mgdv(int matriz[tam][tam])
{
   int l, c, vertice[tam], grau=0;
   system("cls");
   for(l=0; l<tam; l++)
      vertice[l]=0;

   for(l=0; l<tam; l++)
      for(c=0; c<tam; c++)
         if(matriz[l][c] == 1)
            vertice[l]++;

   for(l=0; l<tam; l++)
      if(vertice[l] > grau)
         grau=vertice[l];
   cout<< "\t1\t2\t3\t4\t5\t6\n\n";
   for(l=0; l<tam; l++)
   {
      cout<< l+1<< "\t";
      for(c=0; c<tam; c++)
         cout<< matriz[l][c] << "\t";
      cout<< "\tGrau: " << vertice[l] << "\n";
   }
   cout<< "\n\n\n";
   for(l=0; l<tam; l++)
      if(vertice[l] == grau)
         cout<< "O(s) vertice(s) " << l+1 << " possui o maior grau encontrado: Grau " << grau << "\n";
   cout<< "\n\n";
   system("pause");
}

void stgv(int matriz[tam][tam])
{
   int l, c, vertice[tam], somador=0;
   system("cls");
   for(l=0; l<tam; l++)
      vertice[l]=0;

   for(l=0; l<tam; l++)
      for(c=0; c<tam; c++)
         if(matriz[l][c] == 1)
            vertice[l]++;

   for(l=0; l<tam; l++)
   {
      somador+=vertice[l];
   }

   cout<< "\t1\t2\t3\t4\t5\t6\n\n";
   for(l=0; l<tam; l++)
   {
      cout<< l+1<< "\t";
      for(c=0; c<tam; c++)
         cout<< matriz[l][c] << "\t";
      cout<< "\tGrau: " << vertice[l] << "\n";
   }
   cout<< "\n\n\n";

   cout<< "A soma de todo os graus e :" << somador << "\n";

   cout<< "\n\n";
   system("pause");
}

void hamilton(int aresta[tam])
{
   int l, cont[tam2], control, start, end, get, found;
   do{
      system("cls");
      cout<< "\tEscolha o ponto de partida\n\t";
      cin>> start;
      if(start < 1 || start > 6)
      {
         system("cls");
         cout<< "\n\tO valor da vertice nao pode ser menor do que 1 e maior do que 6\n\n";
         system("pause");
      }
   }while(start < 1 || start > 6);
   do{
      cout<< "\n\tEscolha o ponto onde quer chegar\n\t";
      cin>> end;
      if((start < 1 || start > 6))
      {
         system("cls");
         cout<< "\n\tO valor da vertice nao pode sermanor do que 1 e maior do que 6\n\n";
         system("pause");
      }
      else
         if(start == end)
         {
            system("cls");
            cout<< "\n\tO valor do fim nao pode ser igual ao do inicio\n\n";
            system("pause");
         }
   }while((start < 1 || start > 6) || (start == end));

   for(l=0; l < tam2; l++)
      cont[l]=0;

   found=0;
   get=0;
   control=0;
   l=0;

   while(l < tam2 || get != end)
   {
      if(get != 0 && aresta[l] == get)
      {
            cont[control] = aresta[l];
            control++;
            get = aresta[l+1];
            if(get == end)
            {
               found=1;
               cont[control] = aresta[l+1];
               control++;
            }
      }
      else
         if(get == 0 && aresta[l] == start)
         {
            cont[control] = aresta[l];
            control++;
            get = aresta[l+1];
            if(get == end)
            {
               found=1;
               cont[control] = aresta[l+1];
               control++;
            }
         }
      if(l+1 == tam2 && found == 0)
         l=0;
      else
         l+=2;
   }

   cout<< "Aresta = { ";

   for(l=0; l<tam2; l++)
   {
      if(l % 2 != 0)
      {
         cout<< aresta[l] << "} ";
      }
      else
      {
         cout<< "{" << aresta[l] << ",";
      }
   }
   cout<< " }";

   cout<< "\n\n\n";

   cout<< "Hamilton = { ";
   l=0;
   while(l<tam2 && cont[l] != 0)
   {
      if(l+1 == tam2)
         cout<< cont[l];
      else
         cout<< cont[l] << ", ";
   }
   cout<< " }";

   system("pause");
}
Renancr
Renancr

Mensagens : 118
Data de inscrição : 08/03/2010

Ir para o topo Ir para baixo

Ir para o topo

- Tópicos semelhantes

 
Permissões neste sub-fórum
Não podes responder a tópicos