 Página anterior | Voltar ao início do trabalho | Página seguinte  |
int compara(int *x, int *y) {
if (*x < *y) {
return 1;
}
if (*y > *x) {
return -1;
}
return 0;
}
Sentiram a flexibilidade da minha linguagem?
Bom... Agora vamos entender os outros argumentos do qsort() (esses são fáceis).
O primeiro argumento é o tão esperado vetor (na verdade, um ponteiro pra ele). O segundo é o número de elementos no vetor. O terceiro é o tamanho que um elemento ocupa na memória.
#include <stdio.h>
#include <stdlib.h>
int compara(int *x, int *y) {
if (*x > *y) {
return 1;
}
if (*y > *x) {
return -1;
}
return 0;
}
int main() {
int i, vetor[]={53, 22, 55, 34, 1, 126, 72};
qsort(vetor, 7, sizeof(int), (void *)compara);
for (i=0; i<7; i++) {
printf("%d ", vetor[i]);
}
printf("n");
return 0;
}
Vou neste e nos próximos artigos falar-lhes sobre a Teoria dos Grafos. É uma coisa que poderia ser complicada, então pra facilitar o entendimento eu fiz duas coisas:
Eu baixei um programa brasileiro chamado Rox, que foi feito em Java e é disponibilizado sob a GNU/GPL. Ele serve para facilitar o ensino da "Teoria dos Grafos" ajudando-nos a representar grafos e até executando algoritmos conhecidos de grafos no grafo que criamos.
Resolvi que trabalharemos sempre com exemplos da "vida real". Neste artigo, vamos trabalhar com o Orkut como base, partindo do princípio que todo mundo sabe o que é o Orkut.
Neste primeiro artigo, só falarei sobre a definição do grafo e sua utilidade. Apresentarei as definições de: vértice, aresta, grau, grafo orientado, grau de entrada e grau de saída. Então, vamos lá!
A definição de grafo é muito simples. Segundo o Professor Cid Carvalho de Souza: Uma forma de representar uma relação binária entre elementos de um conjunto. Bom... É simplesmente uma representação de relações (que chamamos de arestas) entre objetos, que chamamos de vértices. Vamos logo ao exemplo: a amizade no Orkut.
Estão vendo esta árvore? Esta é a representação que chamamos de grafo. Vamos supor que este é o grafo das amizades do Orkut e as bolinhas nele são as seguintes pessoas:
Eu (número 1) tenho dois amigos: o João (número 2) e a Maria (número 3), porque estou ligado a eles. O João (número 2) tem três amigos: eu (número 1), a Maria (número 3) e o José (número 4). E assim podemos fazer com os outros contando as linhas que saem de cada pessoa.
Cada pessoa é um vértice e cada linha (relação entre duas pessoas) é uma aresta. Dizemos que é uma relação binária lá em cima, porque a relação é sempre entre dois vértices.
Os números de amigos que cada pessoa tem (o número de relações que cada vértice tem) é o que chamamos de "grau" de um vértice. Grau dos vértices do exemplo acima:
Oras, se você consegue contar as arestas que saem de cada vértice na programação (se você sabe fazer algo básico como calcular o grau de um vértice), você pode oferecer seus serviços ao Google e ganhar milhões, pois, como todos sabem, o Orkut não sabe fazer isso direito! Hehehe...
Brincadeiras a parte... Grafos são extremamente úteis porque são representações bastante simples (você teve dificuldade para entender minha árvore ali em cima?) e essa estrutura deles aparece em muitos problemas computacionais. Além disso, existem muitos algoritmos eficientes para problemas complexos que utilizam estas representações.
Traduzindo os conceitos do Orkut para os grafos:
Um grafo é orientado quando eu sou seu amigo, mas você não é meu amigo. Você sabe que um grafo é orientado quando ele tem "setinhas", como o grafo abaixo.
Vamos supor que isso aí é um mapa do Brasil. Ele despreza as cidades que não são importantes para o país, levando apenas em consideração portanto: São Paulo, Florianópolis e Itajaí.
As arestas indicam que há uma estrada para você ir de uma cidade para a outra, mas só dá pra ir no sentido da estrada, que as setas representam. Portanto, você pode ir de São Paulo, de São Paulo a Itajaí e Florianópolis a Itajaí, mas não de Itajaí para qualquer outro lugar.
Os graus dos vértices neste segundo grafo seriam os seguintes, certo?
Quase... Porém, nos grafos orientados nós temos dois tipos de grau diferentes. Dizemos que:
Portanto, os graus de entrada do nosso grafo são:
E os graus de saída:
2.5 Onde mais posso utilizar grafos?
Existem vários casos onde você vai querer usar grafos:
Como veremos nos próximos artigos, tem algoritmo pra fazer "tudo" em grafos... Então representar alguma coisa em grafos é muito útil pra poder descobrir uma série de coisas.
A maioria das páginas que eu conheço sobre grafos são muito malignas porque apresentam uns 50 conceitos diferentes de grafos juntos (ex.: grafo conexo, grafo desconexo, caminho, ciclo, etc.). Nos meus artigos, devo tratar um assunto de cada vez para facilitar o entendimento. Então, vou parar por aqui hoje.
No próximo artigo: Como representar um grafo na programação? Você já pode ir pensando nisso...
Tiago Madeira - tmadeira[arroba]gmail.com
| Página anterior | Voltar ao início do trabalho | Página seguinte |
|
|
|
