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!

1,736 thoughts on “Representando Grafos na Programação

  1. I enjoy you because of each of your efforts on this website. My mum take interest in making time for research and it’s really simple to grasp why. We notice all concerning the dynamic way you provide informative thoughts on your website and therefore foster response from people about this area while our princess is always studying so much. Take pleasure in the remaining portion of the year. You’re the one doing a powerful job.

  2. did RJ just congratulate himself for saying the Mets would never want Sonny? And his evidence is that the Mets want Lowe? What GM in their right mind would not explore all the possibilities. What is Omar supposed to do if he gets outbid for Lowe and Perez? Is he then just supposed to say “aw shucks, guess no pitchers for us this year”? wow. just wow. DRB is just becoming unreadable. the smugness makes me throw up a little in my mouth. if RJ is going to be smug, at least be smug about something that he can prove is right.

  3. Thanks so much for providing individuals with an extremely brilliant possiblity to read critical reviews from here. It’s usually so brilliant and stuffed with a great time for me and my office friends to visit your web site particularly three times a week to see the new guidance you will have. And definitely, I am just usually fascinated for the good pointers you serve. Selected two points in this article are completely the best we have ever had.

  4. José.Pois é. Grande confusão a minha. É que os acontecimentos estranhos são tantos, e com tal profusão de pormenores, que a minha desgraçada memória já não os consegue albergar com clareza. Imagine que, na imagem do post, quase reconheci o Al Pacino, o Andy García e o Roberto de Niro!

  5. I precisely had to thank you very much all over again. I am not sure the things that I would’ve done in the absence of the entire solutions shared by you about such a topic. It has been a traumatic matter in my position, but being able to view a new expert style you managed that took me to cry with fulfillment. Now i’m happier for your support and in addition sincerely hope you realize what a powerful job you were putting in teaching men and women through the use of your blog. Probably you’ve never got to know all of us.

  6. I am also commenting to make you know what a notable experience my girl experienced using your site. She came to find many details, which included what it’s like to have a great helping mindset to make other individuals without hassle grasp several multifaceted matters. You actually surpassed visitors’ expected results. I appreciate you for supplying these effective, trusted, explanatory and fun tips about your topic to Julie.

  7. Bir ÅŸey çok güzel o da ezmenin zırh ile yapılması. Ankara’da bunu bulmak çok kolay deÄŸil, herkes iÅŸin kolayına kaçıp robot ile çekiyor ezmeyi ki bu malzemenin içindeki tüm suyu ve dolayısı ile lezzeti kaçırıyor.Bir diÄŸer güzel ÅŸey de sumaklı soÄŸan, memlekete kurban bayramına götürdü beni VA:F [1.9.22_1171]please wait…VA:F [1.9.22_1171](from 0 votes)

  8. I precisely desired to appreciate you once more. I’m not certain what I could possibly have done in the absence of the entire points revealed by you directly on my question. It previously was a real horrifying dilemma in my opinion, but noticing this skilled fashion you solved the issue made me to cry over contentment. Now i’m happy for your help and then expect you are aware of a great job that you are accomplishing training most people via your web page. I know that you’ve never encountered any of us.

  9. This would not be HFL without a retarded HD comment that has nothing to do with the article. Sweet.At least you could be funny and make sense.BTW – There is no such thing as an 883 Dark but you may have been confused with your Mom’s ride; the 8″ dark… shaft drive.

  10. fantastic web webpage…Hi! Many every period they get virtually every specific plugins for safeguard when compared with criminals? So this spouse plus personally i believe relatively unique regarding fading off numerous things We all of possess almost all functioned extremel…

  11. I have to show my thanks to you for bailing me out of this setting. As a result of surfing around through the internet and obtaining advice that were not productive, I assumed my entire life was done. Living without the solutions to the difficulties you’ve resolved by way of your short article is a critical case, and ones which could have in a wrong way affected my career if I had not discovered the website. Your main knowledge and kindness in dealing with every part was very useful. I’m not sure what I would’ve done if I had not come across such a step like this. I’m able to now relish my future. Thanks a lot very much for this impressive and result oriented guide. I will not hesitate to recommend the sites to any person who should have guidance about this situation.

  12. Puts up with anythingI had to really think about all these and this just came in my throat so many times. I tend to hold onto and not draw boundaries in my relationships until I am sucked dried. Its really difficult when you are trying to lead in a church.

  13. Lastima siento por usted, y no pienso gastar más tiempo en replicarle, no obstante recojo el testigo gramatical, y le sugiero que se aplique a su libro, es verdad no tiene errores ortográficos, pero si gramaticales, y hágase un digno favor, ponga color a su vida y a su libro. No se preocupe señor ARISTÓCRATA, que no gastare mi tiempo en leer su libro ni en esta página. Reciba una cordial despedida, desde Basel,Suiza.

  14. Basiu, usmażyÅ‚am Å›mietanÄ™! Dla mnie bomba!Pozdrów babciÄ™ HelkÄ™ i podziÄ™kuj.A Łukaszowi buzi podaruj za ten wspaniaÅ‚y makaron! Chociaż jak by sam tak w prezencie zagniótÅ‚,to najlepszy by byÅ‚.Co……….???Buziaki!

  15. Needed to write you one bit of observation to be able to give thanks as before for all the breathtaking knowledge you have featured on this website. It has been certainly unbelievably open-handed of you to provide extensively all a number of us could possibly have made available for an e-book to generate some bucks on their own, most notably considering the fact that you could possibly have tried it in the event you desired. Those creative ideas likewise acted as a good way to fully grasp other people online have the identical keenness really like mine to learn whole lot more with regards to this problem. I know there are lots of more pleasant sessions ahead for folks who go through your site.

  16. Thanks a lot for providing individuals with an extraordinarily breathtaking possiblity to read articles and blog posts from this web site. It is usually so sweet and stuffed with fun for me personally and my office acquaintances to search your blog at least 3 times per week to see the new guides you will have. And lastly, I’m actually motivated with the unbelievable information you give. Some 3 tips in this posting are easily the very best I have had.

  17. I must express my respect for your kindness supporting men who should have guidance on this important area. Your special dedication to passing the solution all-around ended up being remarkably advantageous and have consistently enabled women like me to reach their endeavors. Your personal warm and friendly guidelines implies this much to me and far more to my office colleagues. Thank you; from everyone of us.

  18. Thanks so much for providing individuals with an extremely terrific possiblity to read critical reviews from this website. It is always very useful and as well , packed with a great time for me personally and my office fellow workers to search your blog nearly 3 times per week to read through the fresh things you will have. And of course, I am also always impressed considering the outstanding concepts you serve. Certain two areas in this article are truly the very best I’ve ever had.

  19. An attention-grabbing dialogue is worth comment. I think that it’s best to write more on this matter, it won’t be a taboo subject however usually people are not sufficient to speak on such topics. To the next. Cheers

  20. Johan, så du kommer in på Genusfotografens privata blogg och håller på att uttrycka åsikter om saker och ting? Vad är problemet? Får han inte tycka det är olustiga bilder? Är det förbjudet att skriva blogginlägg som du inte håller med om allt i? Handlar din kritik Johan om att du vill påtvinga Genusfotografen dina värderingar, eller vad är det frågan om?

  21. Ich finde in einer Familie sollte man zusammenhalten und einander unterstützen und gerne haben. Es ist sehr wichtig eine Familie zu haben die einem in Nöten hilft.

  22. I want to show some appreciation to you for bailing me out of this type of problem. As a result of scouting through the the web and meeting principles which were not beneficial, I believed my life was over. Being alive without the solutions to the difficulties you’ve fixed by means of this article is a critical case, as well as those which may have in a negative way damaged my entire career if I hadn’t come across your blog post. Your main competence and kindness in playing with every item was important. I don’t know what I would have done if I hadn’t come across such a point like this. It’s possible to at this time look ahead to my future. Thanks a lot very much for your professional and sensible guide. I won’t hesitate to endorse your web site to anyone who wants and needs guide about this subject.

  23. I wish to express appreciation to this writer just for rescuing me from this particular circumstance. After looking out through the world-wide-web and coming across methods that were not pleasant, I thought my life was well over. Living minus the answers to the issues you’ve resolved all through your entire write-up is a critical case, and ones that could have negatively damaged my entire career if I had not encountered your web site. Your primary know-how and kindness in controlling all the stuff was tremendous. I’m not sure what I would have done if I had not come upon such a step like this. I can at this moment look forward to my future. Thank you so much for the skilled and sensible help. I won’t think twice to recommend your web page to anybody who should have guide about this situation.

  24. I wanted to draft you this little bit of observation just to thank you so much over again on the splendid ideas you have discussed in this case. This is quite seriously generous of people like you to present unreservedly what a lot of folks could have marketed as an electronic book to generate some dough for their own end, specifically given that you might have tried it if you ever desired. The principles in addition acted like a easy way to recognize that other people online have similar interest like my own to know good deal more around this problem. Certainly there are some more pleasant times in the future for those who read carefully your site.

  25. I happen to be commenting to make you understand of the remarkable discovery my friend’s girl enjoyed browsing your web site. She came to find some pieces, which included how it is like to have a great helping spirit to make many more quite simply know a variety of extremely tough issues. You truly surpassed readers’ desires. I appreciate you for producing the warm and helpful, dependable, edifying not to mention cool tips about the topic to Evelyn.

  26. I definitely wanted to develop a quick word so as to appreciate you for these wonderful facts you are placing on this site. My time consuming internet lookup has finally been recognized with pleasant know-how to write about with my company. I ‘d tell you that we website visitors actually are very lucky to be in a fantastic site with so many lovely individuals with very beneficial pointers. I feel very much lucky to have seen your web site and look forward to some more enjoyable moments reading here. Thanks again for everything.

  27. I would like to express some thanks to this writer for rescuing me from this particular condition. Right after checking through the internet and getting ways which were not pleasant, I was thinking my entire life was over. Existing devoid of the approaches to the issues you’ve fixed as a result of your entire guideline is a crucial case, as well as the ones which might have adversely affected my career if I had not come across your blog post. Your good skills and kindness in dealing with the whole thing was invaluable. I’m not sure what I would have done if I hadn’t come across such a solution like this. I can also at this point look ahead to my future. Thanks so much for the impressive and result oriented help. I won’t be reluctant to recommend your web sites to anybody who needs and wants counselling on this problem.

  28. I'd love to visit the West Coast of America for three reasons – dinner at French Laundry, Napa wine country exploring, and the quintessential American road trip experience (from SF to Vegas!)

  29. "that the use of a trade mark used together with the ® symbol suggested two things to the relevant consumers: firstly, the existence of a registered trade mark spelled exactly as used in the advertising and secondly, that the advertiser was authorised to use this mark in its advertisement, either as trade mark owner or licensee."That seems what they looked at and what they wanted to rule on. No mention of "TM". If you use the ® symbol you suggest the existence of a registered trade mark, if there isn't one, you are misleading.Is that of any help?

  30. Thank you for all of your hard work on this site. Ellie really likes conducting investigations and it is simple to grasp why. My spouse and i notice all relating to the lively medium you convey invaluable ideas via the website and in addition increase response from other people about this theme while our own child has always been discovering a lot. Have fun with the remaining portion of the new year. You are always doing a useful job.

  31. Thank you for all your valuable work on this web page. My mom take interest in going through internet research and it’s simple to grasp why. Many of us know all concerning the lively manner you convey informative guides on the web blog and as well foster response from others on that issue then our own daughter is actually discovering a lot of things. Enjoy the remaining portion of the new year. You’re the one conducting a fantastic job.

  32. Thank you a lot for providing individuals with an extremely nice opportunity to check tips from here. It is usually very kind plus full of fun for me personally and my office mates to search your website on the least thrice in a week to find out the newest guides you have got. And indeed, I’m always fulfilled with the attractive hints you serve. Certain 4 facts in this posting are in reality the most effective we have had.

  33. Linda, This poem is awesome! The perfect next installment after the last. You have captured the despair and hopelessness of Miranda’s bipolar mixed state so wonderfully. Can’t wait to see what happens next. Perdamaian, LindaLinda Kruschke baru diposting..

  34. 103Hello, a well written post buddy. Thnx However I am experiencing problem with ur RSS feed. Don’t know why Fail to subscribe. So anybody else experiencing same rss issue? Anyone who knows please respond. Thnkx

  35. Ik gebruik het nu ook al een tijdje, maar niet elke avond want soms vind ik het te veel werk maar ben nog steeds tevreden over ocm :) Anotherfashionlover onlangs geplaatst..

  36. The Prague offensive in 1945, the Soviets outkilled the Germans to hell. Take away prisoners of war people who died during the war. An the 1940, to get a a clear picture. Let’s add the 10 million post war german deaths (3 million military pows) to the Nazi totals during the war. Change your perception. Red Army casaulties inflated during the war BECAUSE OF POWS!

  37. What matters in fact is the self-identification of the people, which fluctuates across generations, and their socio-political will.Right, so you wouldn’t mind if a few Frenchmen decided to secede from France, found a “Basque Republic”, name their Romance language as “the Basque Language”, and claimed that they were the real Basques and people such as yourself were usurpers who oppressed the indigenous Romance-speaking “Basques” of your country?

  38. thought this was a clever way to say what you are thankful for, thank you Blue Cricket Designs for sharing your idea.  A drop cloth is used for this project, but you could easily use butcher

  39. я в шоке от этого магазина! уже 2 месяца не могу посылку получить, на письма не отвечают, в Россию посылка прилетела тока ерез месяц и до сих пор не могу ее получить. Я у китайцев покупала и никада таких проблем не было, а тут такой известный магазин и такой ужасный сервис(( конечно я больше ничего не буду у них заказывать.

  40. It’s a pedantic point I know, and I have no wish to begin a “pedant’s corner” here, but you can not qualify the word unique, such as relatively unique. Something is either unique or it isn’t unique, and doesn’t exist is any other form.Just saying that’s all.   1 likes

  41. ebyou’re really a good web marketer. The site loading speed is awesome. It seems you’re doing virtually any unique strategy. In inclusion, The items are masterwork. you have performed a magnificent job in this matter!21

  42. Angie…I have KIV this :) I have so much of the poppy seeds and I dont know what to do with them other than in cakes :) Thanks for sharing the recipe…lemon and poppy seeds goes well ")

  43. They point out that later studies, which had more data and lower standard errors, did not show the expected increase in t-statistic.Though a serious methodological indictment, opponents of the minimum wage largely ignored this issue; as Thomas C. Leonard noted, "The silence is fairly deafening."=================================Funny, the experts seem to be divided on this point, but a few blooggers here consider it a done deal.I believe there is more to be learned on this subject. We have not yet discovered and accepted the objective truth, or else this conversation would not be happening.

  44. Tous mes voeux, mon cher Henry, que 2012 te soit douce et féconde. Continue à nous ravir de tes conseils et de tes textes.Bravo pour cette fable dont les vers valent tous les éditoriaux et les analyses journalistiques les plus prétentieuses et souvent bien creuses. Et si l’humour torride sauvait la France de cette morosité ravageuse qui l’étreint….

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>