Grafos e suas Aplicações

Grafos e suas Aplicações Grafos são umas das mais versáteis estruturas de dados utilizadas na programação de computadores. Eles geralmente se prestam a resolver problemas de uma categoria diferente das estruturas de dados vistas até agora, visto que, raramente, estes problemas envolvem o armazenamento de números
(como em listas, árvores etc.). Sob o ponto de vista estritamente matemático, listas ligadas e árvores podem ser classificadas como grafos. No entanto, em termos da programação de computadores, grafos são utilizados de maneira diferentes das listas e árvores, visto que estas estruturas têm sua forma ditada pelo algoritmo que irá manipulá­las (a forma de uma árvore binária facilita a pesquisa e inserção de dados dentro dela). Já grafos têm sua forma orientada pelo problema que se propõem a modelar. Por exemplo, um grafo pode modelar um mapa rodoviário (com as cidades e as rodovias que as interligam). Ex:

.

Grafos Um grafo consiste num conjunto de nós (ou vértices ) e num conjunto de arcos (ou arestas ). Cada arco num grafo é especificado por um par de nós. A
Figura 1a, ilustra um grafo. A seqüência de nós é {A, B, C, D, E, F, G, H}, e o conjunto de arcos é {(A,B), (A,D), (A,C), (C,D), (C,F), (E,G), (A,A)}. Se os pares de nós que formam os arcos forem pares ordenados, diz­se que o grafo é um grafo orientado (ou dígrafo). As Figuras 1b, c e d ilustram três dígrafos. As setas entre os nós representam arcos. A ponta de cada seta representa o segundo nó no par ordenado de nós que forma um arco, e o final de cada seta representa o primeiro nó no par.

Figura 1 – Exemplos de grafos

O conjunto de arcos do grafo da Figura 1b é {<A,B>, <A,C>, <A,D>, <C,D>,
<F,C>, <E,G>, <A,A>}. Usamos parênteses para indicar um par