grafo

• GRAFOS
Um grafo nada mais é do que um conjunto de nós (vértices) e em um conjunto de arcos (arestas), onde cada arco em um grafo é especificado por um par de nós. Definição:
• um grafo dirigido(orientado) G é formado por
– um conjunto finito V de vértices
– um conjunto de arestas A
⊆ V × V uma aresta liga ou conecta dois vértices. uma aresta liga ou conecta dois vértices. um grafo não dirigido(grafo não orientado) é um grafo no qual as arestas são pares não ordenados.
Aplicações: grafos são muito utilizados para modelar sistemas reais como por exemplo:
– redes de distribuição de energia, telecomunicações
– malha viária de uma cidade
– circuitos elétricos
– processos industriais
– o grafo é representado por uma matriz quadrada M é 1 ou 0

representação em C
Arestas:
/* representação de uma aresta */ typedef struct edge* apEdge; typedef struct edge { int c; /* 'peso' ou 'custo' associado à aresta */ int v; /* índice do vértice 'destino' */ apEdge next; /* próxima aresta da lista */
} edge; Grafos - representação em C
Vértices:
typedef struct vert* apVert; typedef struct edge* apEdge;
/* descrição de um vértice */ typedef struct vert { int d; /* 'distância' do vértice à 'origem' */ int r; /* próximo vértice no caminho até a origem */ int m; /* vértice marcado ? */ apEdge list; /* lista de arestas */
} vert;
Grafo:
struct vert graph[n];

• Algoritmo de menor caminho O algoritmo de menor caminho (Dijkstra), soluciona o problema do caminho mais curto num grafo dirigido ou não dirigido com arestas de peso não negativo, em tempo computacional O([m+n]log n) onde M é o número de arestas e N é o número de vértices. O Dijkstra Para a teoria dos grafos é uma "estratégia preguiçosa" e é conveniente já que sendo P um menor caminho entre 2 vértices U e V, todo sub-caminho de P é um menor caminho entre 2 vértices pertencentes ao caminho P, desta forma construímos os melhores caminhos dos vértices alcançáveis