GRAFOS

Os grafos são estruturas de dados amplamente utilizadas, mas ao contrário das outras estruturas vistas até agora ele não é uma forma de armazenar dados e sim de solucionar problemas. Pode ser utilizado em varias áreas como num mapa para achar o menor caminho a ser percorrido ou em máquinas para cortar peças de uma prancha (como na fabricação de móveis) com o menor desperdício possível.
O grafo é composto pelo vértice (nó) e a aresta (arco), os vértices são ligados entre si pelas arestas. Um exemplo para entender-mos melhor seria uma cidade (vértice) e uma estrada (aresta), onde a estrada liga a cidade a outras, ele pode ser mão única, ou seja, você pode sair de uma cidade pra outra mas não pode voltar por ela, em grafos isso é chamado de arco "dirigido" é representado com uma seta mostrando a direção, também pode existir uma aresta "não dirigida" sem seta, onde se pode ir e voltar pelo mesmo arco.caso haja apenas uma aresta dirigida o grafo será considerado dirigido.

A 1ª aplicação de grafos foi feita por Euler, provando que só é possível percorrer todos os nós de um grafo sem repetir nenhuma aresta retornando ao vértice de origem, se o grau (nº de arcos ligados a um nó) seja par, esse conceito é denominado caminho euleriano.