Grafos

• 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