Representando Grafos na Programação

No último artigo, conhecemos a representação chamada “grafo” da seguinte maneira:

Exemplo 1

Como todos sabemos, seria bem difícil trabalhar uma árvore assim na programação! :D Por isso, existem várias maneiras de representar um grafo. Nesta série só vou usar as duas mais populares:

  • Matriz de Adjacência
  • Lista de Adjacência

Poderíamos falar também sobre a Matriz de Incidência, mas eu nunca precisei utilizá-la, então prefiro só entrar nessas duas mesmo.

Cada vértice é um número

Para representar um grafo, cada vértice sempre vai ser um número. No caso de você querer representar amizade entre duas pessoas, como no exemplo do Orkut no último artigo, você cria um vetor chamado nome[] que contém o nome de cada número… :)

Matriz de Adjacência

A matriz de adjacência é uma matriz de N x N (onde N é o número de vértices do grafo). Ela inicialmente é preenchida toda com 0 e quando há uma relação entre o vértice do x (número da coluna) com o do y (número da linha), matriz[x][y] é marcado um 1.

Vamos escrever este grafo aqui usando uma matriz de adjacência:

Matriz Inicial

  1 2 3 4 5
1 0 0 0 0 0
2 0 0 0 0 0
3 0 0 0 0 0
4 0 0 0 0 0
5 0 0 0 0 0

Relações do nosso grafo

Já que o grafo não é orientado, a relação 1-2 significa 2-1 também. :)

  • 1-2 (2-1)
  • 1-3 (3-1)
  • 2-3 (3-2)
  • 2-4 (4-2)
  • 4-5 (5-4)

Essas são as cinco arestas do nosso grafo. Vamos representá-la na matriz de adjacência:

  1 2 3 4 5
1 0 1 1 0 0
2 1 0 1 1 0
3 1 1 0 0 0
4 0 1 0 0 1
5 0 0 0 1 0

Simetria

Uma das características da matriz de adjacência quando o grafo não é orientado é a simetria encontrada na “diagonal”. É interessante que se lermos uma coluna de índice v ou uma linha de índice v vamos encontrar a mesma coisa.

Problemas da OBI

Alguns desses programas são complicados, mas isto não entra em questão. Apenas dê uma olhada no recebimento da entrada deles. Todos estão em C. O que eles têm em comum é a utilização de uma matriz de adjacência para guardar o grafo (geralmente nomeada g):

* – Grafo orientado
+ – Grafo ponderado (veremos no próximo artigo)
X – Não queira ver esse problema. Nunca vi solução mais feia. Já estou providenciando uma implementação mais decente… ;)

Descobrir o grau de cada vértice

Eu não disse pra vocês que era fácil conseguir emprego no Orkut? Hehehe… Vamos pensar como podemos descobrir o grau (relembrando… o número de arestas que cada vértice tem OU o número de amigos que cada pessoa tem) na matriz de adjacências. Não basta contar quantos 1s tem na sua linha correspondente? Então façamos isto.

para i [tex]\leftarrow{}[/tex] 1 até N, faça
	grau [tex]\leftarrow{}[/tex] 0
	para j [tex]\leftarrow{}[/tex] 1 até N, faça
		se matriz[i][j] = 1, então
			grau [tex]\leftarrow{}[/tex] grau + 1
		fim-se
	fim-para
	imprima "O vértice " i " tem grau " grau "."
fim-para

O custo é [tex]\Theta{}(n^{2})[/tex] até no melhor caso… Será que não há uma maneira mais simples de fazer isso? Imagina um negócio do tamanho do Orkut. Milhões de pessoas… Não seria bem mais fácil se ao invés de termos que passar por todos os vértices, só passarmos pelos amigos? Não poderíamos colocar somente seus amigos num vetor? É por isto que utilizamos a lista de adjacência.

Lista de Adjacência

A lista de adjacência consiste em criar um vetor para cada vértice. Este vetor contém cada vértice que o vértice “conhece” (tem uma aresta para). Geralmente é representada com uma matriz, porque cada vértice vai precisar de um vetor diferente, não é? Já que eu não vou ser duas vezes “amigo” de ninguém, então podemos fazer uma matriz de NxN.

  1 2 3 4 5
1          
2          
3          
4          
5          

A lista consiste em escrever para cada número de linha (= vértice) seus amigos, da seguinte maneira:

  1. 2, 3
  2. 1, 3, 4
  3. 1, 2
  4. 2, 5
  5. 4

Portanto, na programação seria representado da seguinte maneira:

  1 2 3 4 5
1 2 3      
2 1 3 4    
3 1 2      
4 2 5      
5 4        

O método da lista de adjacências tem várias vantagens: dependendo de como você implementa você não precisa inicializar a lista (zerar), as buscas são bem mais rápidas (você só passa pelos vértices que são “amigos” do atual) e geralmente você já tem o grau do vértice na ponta da língua (eu, pelo menos, sempre uso um vetor cont que contém o número de amigos de cada vértice para ficar mais fácil inserir o próximo elemento na lista – lista[cont[v]++]=w).

Como implementar

Vamos trabalhar com uma entrada de vários x, y, indicando relação entre x-y (y-x) até que x=0 e y=0. O grafo não é orientado.

Matriz de Adjacências

para i [tex]\leftarrow{}[/tex] 1 até N, faça
	para j [tex]\leftarrow{}[/tex] 1 até N, faça
		matriz[i][j] [tex]\leftarrow{}[/tex] 0
	fim-para
fim-para

enquanto (recebe x, y e x [tex]\neq{}[/tex] 0), faça
	matriz[x][y] [tex]\leftarrow{}[/tex] 1
	matriz[y][x] [tex]\leftarrow{}[/tex] 1
fim-enquanto

Tem vários exemplos implementados em C aqui.

Lista de Adjacências

para i [tex]\leftarrow{}[/tex] 1 até N, faça
	grau[i] [tex]\leftarrow{}[/tex] 0
fim-para

enquanto (recebe x, y e x [tex]\neq{}[/tex] 0), faça
	lista[x][grau[x]++] [tex]\leftarrow{}[/tex] y
	lista[y][grau[y]++] [tex]\leftarrow{}[/tex] x
fim-enquanto

Para quem não programa em C, o variavel++ significa “incrementar variavel depois da instrução atual”.

As duas juntas

para i [tex]\leftarrow{}[/tex] 1 até N, faça
	para j [tex]\leftarrow{}[/tex] 1 até N, faça
		matriz[i][j] [tex]\leftarrow{}[/tex] 0
	fim-para
	grau[i] [tex]\leftarrow{}[/tex] 0
fim-para

enquanto (recebe x, y e x [tex]\neq{}[/tex] 0), faça
	matriz[x][y] [tex]\leftarrow{}[/tex] 1
	matriz[y][x] [tex]\leftarrow{}[/tex] 1
	lista[x][grau[x]++] [tex]\leftarrow{}[/tex] y
	lista[y][grau[y]++] [tex]\leftarrow{}[/tex] x
fim-enquanto

Qual a representação que devo utilizar?

Isso depende totalmente do problema. Em alguns casos, o mais barato é usar as duas representações juntas. As vantagens da lista de adjacências eu já escrevi aqui. A única vantagem da matriz de adjacências é você em tempo constante (não é nem linear) saber se um vértice é amigo de outro. Afinal, basta testar matriz[v][w].

Até maio do ano passado, eu não tinha aprendido isso direito e sempre usava a matriz de adjacências. Por isso muitos dos meus problemas estão resolvidos de forma pouco eficiente… e isso pode ser crucial numa prova. Por isso, saiba usar as duas formas!

673 thoughts on “Representando Grafos na Programação

  1. I would like to voice my love for your generosity for men and women who must have help on this important content. Your special dedication to getting the message throughout had been rather effective and have truly permitted many people like me to arrive at their goals. The warm and helpful instruction denotes so much a person like me and far more to my fellow workers. Many thanks; from each one of us.

  2. I looked into the Dr Lowe range of product and wanted to know which products do you really like?I am visiting the UK in October and I might pick up a few things. So far I like the sound of the Hydrating cleanser, Dermabrasion Peel and the Moisture Mask.

  3. hey!come online someday…we’ll talk about swades. ;) man…i have just one wish now…….a whole week to be jobless!!! and i say, JOBLESS!!!i’d love to come to all those places you wanted me to come along….and guess what, i’m not going to the a.r.rahman concert here… :’( sniff, sniff!!

  4. A lot of thanks for your own efforts on this website. My daughter really likes managing investigation and it’s simple to grasp why. My spouse and i know all about the powerful tactic you render good guidance via your web site and in addition increase participation from some other people on the idea so our child has been being taught a great deal. Enjoy the rest of the year. You are doing a fantastic job.

  5. I enjoy you because of all of the labor on this site. Kate delights in doing investigation and it’s simple to grasp why. Most people know all about the lively form you provide good tactics by means of this blog and as well improve participation from others on the subject plus our favorite princess is actually starting to learn a lot of things. Enjoy the remaining portion of the year. You are performing a tremendous job.

  6. 15fIch bin mir nicht sicher, ob das was ich zu sehen glaube das ist, was ich sehen könnte wenn ich es verstünde…und bitte deshalb um Hilfe per Mail.Ansonsten Kompliment für den tollen Blog. Hab ihn mir sofort “gebookmarked”. Auch das Kuchen Krümel Bild gefällt mir sehr gut…

  7. I discovered your weblog web site on google and verify just a few of your early posts. Continue to keep up the superb operate. I just further up your RSS feed to my MSN News Reader. Searching for forward to studying extra from you afterward!?

  8. Scrivi il tuo commento Puoi usare questi tags HTML : <a> <abbr> <acronym> <b> <blockquote> <cite> <code> <del> <em> <i> <q> <strike> <strong> Notify me of follow-up comments by email. Notificami nuovi articoli tramite email.

  9. Thank you so much for giving everyone a very nice possiblity to read critical reviews from this web site. It is often so cool plus packed with a lot of fun for me personally and my office acquaintances to visit your web site at a minimum thrice in a week to learn the latest things you will have. And indeed, we are always pleased with all the wonderful tips served by you. Some 2 facts in this article are particularly the simplest we have ever had.

  10. How true the facts express in this film! The worst of all: the stereotypes and discrimination come from the institutions. The scarce-ones that had been able to pass through all the obstacles, realize almost immediately that the Canadian population is very welcoming to the international medical graduates.Do not give-up!

  11. Hallo Frauke (bekannterweise) und Team (unbekannterweise): Ich wünsche ganz viel Spaß und Erfolg – ein tolles Projekt! Ich drücke die Daumen! Dann via Solar-Lovis in die Arktis…? Wäre dann das nächste Rumknobel-Projekt zum Thema nachhaltiges Segeln! Ganz viel Sonne wünscht Anna

  12. Thank you a lot for providing individuals with an extremely marvellous chance to read in detail from this site. It can be so excellent and as well , full of a good time for me and my office acquaintances to visit your blog at a minimum 3 times in 7 days to read the fresh stuff you will have. And indeed, we’re always fascinated with the superb methods served by you. Some 1 areas in this post are in fact the most beneficial I have ever had.

  13. 25 julio, 2007AnónimoBueno latas, mi enhorabuena por la criatura. Cada vez tiene mejor pinta. 8) Ahora, una pequeña cuestion : Intento instalar (nada mas salir, curiosidad malsana) tus nuevas versiones para ver las mejoras, y cada vez tengo que desinstalar la anterior versión. Supongo que esto es común a todos los usuarios. Por lo que para instalar una nueva versión, y si es preciso desinstalar la anterior, ¿no lo podría realizar el mismo ANT? 8) Thanks  

  14. Elque. Mimas, se merece otro artículo como éste. Ya que lo dices, te prometo que haremos un estudio a fondo de Mimas. Ofrece patrones de artificialidad análogos a Iapetus. Sucede que ha sido menos estudiado, pero nos ponemos con él inmediatamente. Te lo prometo.Un saludo.

  15. I don’t think anyone among your contemporaries has ever written about this period, one that I find endlessly fascinating. Reading about your adventures on the East and West coast remind me so much of Jack Kerouac’s On the Road! Maybe one day you could expand all this into a book with illustrations, I have a hunch it would become a bestseller.

  16. Thank your Christi for sharing what you look for. I too like one-of-a-kind art. It feels like it was meant just for me, and knowing it is the only one out there makes it that more special to me! I wish you were near to visit too! It’s going to be so much fun! Thank you for the positive energy. : )

  17. My husband and i were so satisfied when Peter managed to finish off his basic research from the ideas he grabbed through the weblog. It is now and again perplexing just to always be offering helpful hints some other people might have been making money from. And we all know we have got the blog owner to give thanks to for this. All the explanations you have made, the simple site navigation, the friendships you can assist to foster – it is many amazing, and it’s really aiding our son and our family reason why the topic is brilliant, which is wonderfully vital. Thanks for all the pieces!

  18. I and my friends have been checking the nice things on your web page then unexpectedly got an awful suspicion I had not expressed respect to the web site owner for those tips. These young men became for this reason glad to read through all of them and have in effect truly been loving these things. We appreciate you getting very helpful and for deciding on varieties of brilliant useful guides millions of individuals are really eager to understand about. Our own sincere apologies for not expressing appreciation to sooner.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>