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!

4,419 thoughts on “Representando Grafos na Programação

  1. I wanted to draft you that very little observation to give many thanks yet again on the extraordinary advice you have contributed on this page. It’s seriously generous of people like you to give openly all a few individuals could possibly have supplied as an e-book to earn some money for themselves, even more so considering that you might well have tried it in the event you decided. Those solutions as well served as the great way to be sure that other individuals have a similar keenness just like mine to find out more with respect to this condition. I’m certain there are many more pleasurable opportunities ahead for individuals that find out your website.

  2. I precisely wished to appreciate you again. I am not sure the things that I would have achieved without those hints shown by you concerning such problem. It truly was a troublesome condition in my position, however , seeing a well-written avenue you solved it forced me to jump for delight. Now i am happy for the work as well as expect you recognize what a great job that you’re providing educating the others all through your blog. Probably you have never met any of us.

  3. I simply had to thank you so much again. I am not sure the things that I would’ve implemented in the absence of the type of concepts provided by you about my field. It has been a very traumatic circumstance for me personally, nevertheless understanding the very specialised fashion you handled the issue made me to weep with contentment. I will be thankful for the assistance and even sincerely hope you find out what an amazing job you happen to be getting into training other individuals all through your websites. Most probably you have never met any of us.

  4. Paykasa yüzbinlerce platformda alışverişlerde kullanabileceğiniz ön ödemeli bir karttır.
    Paykasa kart kullanıcıları basit işlem yapmak ve güvenli alışveriş için online alışverişlerde paykasa kartı tercih etmektedirler. paykasa al firması olarak bizlerden güvenli bir şekilde satın alanilirsiniz.

  5. I’m writing to let you understand of the beneficial experience my child obtained studying your webblog. She came to find plenty of issues, most notably what it is like to possess a very effective helping spirit to let other people with no trouble completely grasp various complex topics. You really exceeded people’s expectations. Thanks for imparting such helpful, trustworthy, edifying not to mention fun thoughts on your topic to Tanya.

  6. Howdy! This post could not be written any better! Reading through this post reminds me of my previous roommate! He always kept preaching about this. I most certainly will forward this information to him. Fairly certain he’ll have a great read. Thanks for sharing!

  7. I’m also writing to make you know of the perfect discovery my friend’s girl obtained browsing your webblog. She came to find lots of pieces, with the inclusion of how it is like to possess a very effective teaching mood to have folks clearly master selected problematic subject matter. You truly did more than her desires. I appreciate you for imparting these helpful, trusted, revealing and easy tips on your topic to Tanya.

  8. I intended to send you the tiny note to finally thank you very much the moment again over the gorgeous tips you have contributed at this time. This is unbelievably open-handed of you to offer easily what exactly a few individuals would’ve advertised as an e-book to make some money for their own end, even more so now that you might well have tried it in the event you decided. These smart ideas additionally served to be a good way to be sure that some people have similar eagerness similar to my personal own to grasp very much more concerning this issue. I think there are thousands of more enjoyable moments up front for people who look into your blog.

  9. This is the suitable blog for anybody who wants to search out out about this topic. You realize so much its virtually hard to argue with you (not that I truly would need…HaHa). You undoubtedly put a brand new spin on a subject thats been written about for years. Nice stuff, simply great!

  10. I just wanted to type a brief remark to be able to say thanks to you for all the splendid hints you are placing at this website. My rather long internet investigation has at the end of the day been compensated with beneficial facts and strategies to go over with my co-workers. I ‘d admit that many of us website visitors are unequivocally endowed to exist in a really good place with so many outstanding people with beneficial things. I feel rather grateful to have used your website page and look forward to so many more entertaining moments reading here. Thanks a lot again for a lot of things.

  11. My spouse and i felt now thankful when Edward managed to carry out his researching with the precious recommendations he came across when using the site. It’s not at all simplistic just to always be giving for free key points the rest have been selling. And now we remember we need the website owner to give thanks to for that. The specific illustrations you made, the straightforward blog menu, the relationships you can give support to engender – it’s got most astonishing, and it is helping our son and us consider that the topic is brilliant, and that’s quite mandatory. Many thanks for the whole thing!

  12. I simply desired to thank you so much again. I do not know the things I might have tried without those methods revealed by you relating to such situation. It had been a very distressing concern in my view, nevertheless observing your specialised approach you handled the issue took me to weep for happiness. I will be happier for this service and even trust you comprehend what a powerful job that you’re doing teaching the mediocre ones via your web page. I am certain you have never encountered any of us.

  13. 7. We can create or edit your existing artwork designs the same day for those critical urgent orders.8. Upon request we can send you recent samples of custom printed tape runs we have completed for many of our clients.

  14. Now you can buy free viagra and custom printed adult tapes online. We are the UK’s leading adult toy manufacturer. UKPRINTEDTAPE.CO.UK adult chat and dating .

  15. I precisely wanted to thank you very much once again. I’m not certain the things that I might have carried out without those recommendations provided by you directly on that field. It was an absolute hard dilemma for me, but seeing the very well-written avenue you processed the issue forced me to jump with delight. I am just happier for this help and thus believe you really know what a powerful job you were carrying out educating most people via a blog. Most probably you haven’t got to know any of us.

  16. Thank you so much for providing individuals with an extraordinarily spectacular opportunity to read from this site. It’s always very terrific plus packed with a great time for me and my office colleagues to visit the blog at the least thrice in a week to read the newest items you will have. Not to mention, I’m so actually happy with your fabulous secrets served by you. Selected 4 areas on this page are indeed the most suitable I have ever had.

  17. Good point! Interesting tips over this website. It’s pretty worth enough for me. Personally, if all web owners and bloggers made good content as you did, the web will be a lot more useful than ever before. I couldn’t refrain from commenting. I have spent some hours searching for such article. I’ll also share it with a couple of friends interested in it. I’ve just bookmarked this website. Finished with the search done, I will watch some live trans cams. Thank you!! Greetings from San Francisco!

  18. Thank you a lot for providing individuals with a very wonderful possiblity to read critical reviews from this blog. It can be so beneficial and as well , jam-packed with amusement for me and my office fellow workers to visit your web site at the least thrice in a week to read the new secrets you have got. And lastly, I’m just always amazed with all the good information you give. Some 2 tips in this post are clearly the most efficient we have ever had.

  19. I simply had to appreciate you all over again. I do not know the things that I could possibly have sorted out in the absence of the entire techniques documented by you relating to my concern. It was before a depressing condition in my view, however , viewing a expert form you solved that forced me to cry for fulfillment. I am just grateful for the support and in addition wish you are aware of an amazing job you have been putting in instructing people with the aid of your web page. Probably you’ve never met any of us.

  20. There are certainly numerous details like that to take into consideration. That could be a nice level to deliver up. I supply the ideas above as basic inspiration but clearly there are questions like the one you carry up where crucial thing can be working in honest good faith. I don?t know if finest practices have emerged around issues like that, but I am sure that your job is clearly identified as a good game. Each boys and girls really feel the impact of only a second’s pleasure, for the remainder of their lives.

  21. I was more than happy to seek out this internet-site.I wanted to thanks on your time for this glorious learn!! I undoubtedly having fun with each little bit of it and I’ve you bookmarked to take a look at new stuff you blog post.

  22. I precisely had to say thanks once again. I am not sure the things I would have undertaken in the absence of the type of aspects contributed by you directly on this subject. It has been a terrifying matter for me personally, but taking a look at your skilled strategy you treated the issue took me to weep over delight. I will be thankful for this guidance and in addition trust you know what an amazing job your are undertaking instructing the mediocre ones with the aid of your blog. I am certain you have never come across all of us.

  23. There are some attention-grabbing points in time in this article however I don’t know if I see all of them middle to heart. There may be some validity but I’ll take hold opinion till I look into it further. Good article , thanks and we want more! Added to FeedBurner as well

  24. I precisely needed to thank you very much again. I am not sure what I might have tried in the absence of the creative concepts discussed by you concerning this subject matter. It had become the frightening circumstance in my view, but finding out a professional strategy you processed the issue forced me to jump for contentment. Now i’m happy for your work and then wish you really know what a great job you have been undertaking training people today via your web blog. I’m certain you haven’t met all of us.

  25. Hm, i´m also a lil bit confused because of that failure topic. I noticed that Kevin completed every single repetition in his videos. I personally train very often till i can´t move the damn bar anymore…because in my opinion it is not too important to do exactly 10 or 8 or 12 reps because my body isn´t able to count -.-To be honest i´m not sure at all if this makes sense or not Would be cool if Kevin could tell us something about it.

  26. I would like to show my appreciation to this writer just for bailing me out of such a challenge. Just after surfing around throughout the world wide web and getting concepts which are not helpful, I was thinking my life was done. Living minus the approaches to the difficulties you’ve resolved through the posting is a serious case, and ones that would have negatively affected my career if I hadn’t noticed your web site. Your expertise and kindness in touching all areas was very helpful. I am not sure what I would have done if I had not encountered such a solution like this. I’m able to at this moment relish my future. Thanks for your time so much for this reliable and amazing guide. I won’t hesitate to refer your web blog to anyone who needs and wants tips on this subject.

  27. dibah suka naik lorinaik lori tok niaga kasut kat bazar nantifazura amat cantik sekalijap lagi pasti ada “fazura the gundek” dtg membencip/s : “fazura the gundeks” sdg dlm proses nak tyg super imposed gambar fazura lg la tu.. muehehehhheheh…Well-loved.

  28. I wanted to post you this tiny remark to finally say thank you again on the lovely concepts you’ve documented at this time. It is so seriously open-handed with people like you to give unhampered what exactly a few individuals might have marketed for an electronic book to get some money on their own, most importantly considering the fact that you could have tried it if you wanted. These guidelines likewise worked as a fantastic way to recognize that someone else have the identical desire like my own to see good deal more concerning this matter. I’m certain there are numerous more pleasurable sessions in the future for those who browse through your site.

  29. However, it is possible to keep from placing the bets if you happen to would not
    have enough funds. So if you happen to be aiming to make probably the most of it, the time has come to perform
    so. Place your chip on the intersection of vertical
    and horizontal lines inside the table. https://7elm5.com/thekingcasino

  30. Thanks a lot for providing individuals with remarkably brilliant chance to read critical reviews from this website. It is always very brilliant and as well , jam-packed with a lot of fun for me and my office peers to visit the blog no less than three times every week to find out the latest secrets you will have. And of course, we are at all times amazed with your outstanding strategies served by you. Some two ideas in this article are ultimately the best I’ve ever had.

  31. Youre so cool! I dont suppose Ive read anything like this before. So good to seek out any individual with some authentic ideas on this subject. realy thank you for starting this up. this web site is one thing that’s wanted on the web, somebody with a little originality. helpful job for bringing something new to the web!

  32. Thank you for your own effort on this web site. Betty take interest in conducting investigations and it’s really easy to understand why. I notice all concerning the powerful manner you provide practical ideas on this blog and as well attract participation from website visitors on this theme and our simple princess is truly discovering a great deal. Enjoy the rest of the year. You’re carrying out a fantastic job.

  33. Thanks so much for providing individuals with such a terrific chance to read in detail from this site. It really is so lovely and also jam-packed with fun for me and my office acquaintances to visit your site minimum thrice weekly to learn the latest stuff you will have. And indeed, we’re usually amazed with the breathtaking strategies served by you. Some 2 facts in this article are clearly the best I have ever had.

  34.   April 4, 2011Thanks for this great opportunity, Glennis! We hope the ladies of G.L.O.C. enjoy this sneak peek into Comedivaland and will pop in to say hello! Ladies, let us know if you have any web series-making questions, we’re happy to answer!love,comediva

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>