Teoria dos grafos

Programação
#1

Pessoal como eu coloco essa imagem em grafos na prática para colocar essas dados na prática fazendo com que vértices sejam enumeradas e podem ser de peso iguais…estou fazendo a parada é não sei como represento dentro do grafo tem que ser baseada nessa imagem…alguem tem alguma dica ou ideia??20171205_080411

#2

Seria a estrutura de dados? Se for, tem várias formas de fazer isso.

Uma bem simples é perceber que isso se parece com um mapa ou tabela (ou matriz):

class Vertice {
  // direções das arestas, se cada aresta possuir peso, troque for int, valor -1 ou nulo seria não ter seta
  boolean N;
  boolean NE;
  boolean E;
  boolean SE;
  boolean S;
  boolean SO;
  boolean O;
  boolean NO;

  int peso;
  int id;
}

class Grafo {
  Vertice vértices[4][7];
}

int calculaId(int linha, int coluna) {
  return linha * vértices[0].length + coluna;
}

int calculaLinha(int id) {
  return id / vértices[0].length;
}

int calculaColuna(int id) {
  return id % vértices[0].length;
}
#3

Em grafos não existe o conceito de sentido nas arestas (N, S, E, etc.), basta identificar cada vértice. Basicamente existem duas maneira de se representar um grafo: matriz de pesos ou lista de adjacências. A representação pela matriz é bem simples: para um grafo de N arestas você cria uma matriz g NxN. Cada posição g[i,j] da matriz representa uma aresta, ou adjacência. Se o valor da posição g[i,j] é um número, então este é o peso da aresta que vai de i até j. Se não existe aresta ligando i e j, o valor de g[i,j] pode ser 0, null ou ainda algum valor representado infinito.
Se o grafo é não-direcionado, então g[i,j] = g[j,i] para todo i e j.

1 curtida
#4

moral como posso fazer caminhos minimos sem o algoritmos prontos tipo o Dijkstra, eu nao posso usar esses tipos de algoritmos como posso fazer?

#5

Cara, você tem que raciocinar um pouco também, se o Dijkstra conseguiu você também consegue. Se o professor pediu para não usar nada pronto a inteção é estimular o raciocínio, mesmo que você não chegue na solução perfeita.

#6

entao cara eu so queiria uma dica de como comecar nao quero nada pronto nao pois quero aprender tbm