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. My brother suggestedrecommended I might like this blogwebsiteweb site. He was totallyentirely right. This post actuallytruly made my day. You cann’tcan not imagine justsimply how much time I had spent for this informationinfo! Thanks!

  2. I together with my friends were found to be reading through the good strategies located on your web page and so unexpectedly got a terrible feeling I never thanked the blog owner for those strategies. Those ladies became warmed to read them and now have without a doubt been taking advantage of them. Thank you for being so considerate and also for going for this kind of good subjects most people are really needing to be informed on. My honest apologies for not saying thanks to sooner.

  3. I definitely wanted to construct a small message in order to say thanks to you for the amazing tricks you are writing at this site. My time intensive internet lookup has at the end of the day been rewarded with good quality suggestions to share with my friends. I ‘d say that most of us site visitors actually are very lucky to exist in a fine site with many outstanding individuals with great strategies. I feel very lucky to have encountered your web pages and look forward to really more fabulous moments reading here. Thanks once more for everything.

  4. A formidable share, I simply given this onto a colleague who was doing just a little analysis on this. And he in reality bought me breakfast as a result of I discovered it for him.. smile. So let me reword that: Thnx for the treat! However yeah Thnkx for spending the time to debate this, I feel strongly about it and love studying extra on this topic. If possible, as you develop into expertise, would you mind updating your blog with more particulars? It’s extremely helpful for me. Large thumb up for this blog publish!

  5. I do consider all of the ideas you’ve presented in your post. They’re really convincing and will certainly work. Still, the posts are very brief for beginners. May you please prolong them a bit from next time? Thank you for the post.

  6. I simply wanted to write a comment so as to appreciate you for some of the remarkable steps you are giving on this website. My time-consuming internet investigation has at the end been honored with professional suggestions to write about with my friends and classmates. I ‘d point out that we readers actually are really endowed to live in a great place with so many brilliant individuals with beneficial principles. I feel extremely grateful to have come across the weblog and look forward to really more awesome minutes reading here. Thanks a lot once more for a lot of things.

  7. Thank you, I have just been looking for info approximately this topic for
    a while and yours is the greatest I’ve found out till now.

    But, what in regards to the bottom line? Are you sure concerning
    the supply?

  8. This is my first time I have visited your site. I found a lot of interesting information in your blog. From the tons of comments on your posts, I guess I am not the only one! keep up the great work.

  9. I simply want to mention I’m beginner to blogging and definitely savored this web-site. Very likely I’m want to bookmark your blog . You surely come with awesome posts. Thank you for revealing your web site.

  10. Apple Support – Apple is a brand which is known to design a perfect product that matches the need of users perfectly. They work efficiently on design and security to leave no loose end to quality. The computer market is highly influenced by Apple Products. The powerful yet elegant computers designed by Apple makes it one of a kind.

  11. 它讓神經原在常規的緊張鍛煉中進行共振燃燒,由此帶來健身運動所無法達到的效果。Ion Magnum複雜的振動波是基于於二十多年對神經原燃燒信號的研究手工製作的。 設備製造者的臨床研究結果顯示,30分鐘的治療相當於在健身房10個小時的運動,可以燃燒高達5000卡路里的熱量。其他臨床研究顯示肌肉生成的速度以及脂肪(表面脂肪以及深部脂肪)减少的速度相應都比運動的效果更好。對於Ion Magnum沒有進行理療的部位,甚至會有抗衰老防氧化的效果。 有受試者治療一次之後同一個部位减掉了3-4英寸(不像其他减肥治療中宣稱的那樣,一次治療减掉了5英寸,但那是全身20多個部位加起來减掉的尺寸)。同時,它還可以减掉脖子和下巴的脂肪,讓你的雙下巴消失 . 每次治療需要25分鐘。治療前後的效果非常明顯,而且會持續1-2天。要想達到更好的效果,最好接受1-2個小時的治療。

  12. Outstanding post, I think website owners should learn a lot from this blog its real user genial. So much wonderful info on here :D .

  13. 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!

  14. Thank you for your own work on this site. My daughter takes pleasure in managing investigations and it is easy to understand why. Many of us notice all concerning the dynamic manner you make powerful tricks by means of your website and therefore foster contribution from the others about this issue while my princess is truly becoming educated a lot. Take advantage of the remaining portion of the year. You’re doing a fantastic job.

  15. I intended to put you the little note to finally say thanks a lot as before for your personal nice solutions you’ve provided on this site. It’s simply remarkably open-handed with you to give openly just what most of us would’ve offered for an electronic book to help make some money on their own, and in particular given that you might have tried it in case you considered necessary. These advice likewise served to be the great way to fully grasp many people have similar keenness really like my very own to learn significantly more with regards to this issue. I know there are a lot more fun instances up front for individuals that looked at your website.

  16. Magnificent beat ! Ӏ ԝould ⅼike tο apprentice while yoᥙ amend your website,
    how cɑn i subscribe for a blog web site? The account helped mе a acceptable deal.
    Ι had been tiny bit acquainted of thіs уour
    broadcast рrovided bright clear idea

  17. Do you mind if I quote a couple of your posts as long as I provide credit and
    sources back to your webpage? My blog site is in the very
    same area of interest as yours and my users would really benefit from a lot of the information you
    provide here. Please let me know if this alright with you.
    Thanks a lot!

  18. I would like to thnkx for the efforts you have put in writing this blog. I’m hoping the same high-grade website post from you in the upcoming also. In fact your creative writing skills has encouraged me to get my own blog now. Actually the blogging is spreading its wings rapidly. Your write up is a great example of it.

  19. You actually make it appear really easy with your presentation but I in finding this topic to be really something that I believe I would never understand. It kind of feels too complex and extremely broad for me. I am taking a look forward in your next publish, I’ll attempt to get the dangle of it!

  20. Somebody essentially help to make seriously articles I would state. This is the very first time I frequented your web page and thus far? I surprised with the research you made to create this particular publish amazing. Fantastic job!

  21. Needed to write you the very small remark to be able to thank you very much yet again for all the exceptional tricks you have contributed on this website. It was quite wonderfully generous with you to convey extensively what exactly numerous people could have sold as an ebook to help with making some profit on their own, primarily now that you could have done it in case you wanted. The principles also served to provide a great way to fully grasp some people have similar dreams really like mine to figure out many more with respect to this problem. I think there are lots of more fun situations in the future for individuals that scan through your blog post.

  22. This design is steller! You certainly know how to keep a reader entertained. Between your wit and your videos, I was almost moved to start my own blog (well, almost…HaHa!) Wonderful job. I really loved what you had to say, and more than that, how you presented it. Too cool!

  23. Your style is very unique in comparison to other people I have
    read stuff from. Thank you for posting when you have the opportunity, Guess I’ll just bookmark
    this page.

  24. I actually wanted to make a message in order to express gratitude to you for all of the marvelous information you are giving out at this website. My extended internet lookup has finally been paid with brilliant information to write about with my relatives. I ‘d tell you that we visitors are really blessed to be in a great site with so many lovely professionals with good guidelines. I feel extremely privileged to have encountered the webpage and look forward to really more fun times reading here. Thanks once more for everything.

  25. Thanks for your entire work on this site. Ellie really likes making time for internet research and it’s easy to understand why. Most people know all regarding the compelling mode you present sensible techniques by means of this website and therefore cause participation from some other people on this issue and my child has always been starting to learn a lot of things. Take pleasure in the rest of the new year. You’re performing a fabulous job.

  26. FineScan 會在肌膚上製造數以千計的細小深入傷口,即所謂的顯微加熱區(microthermal zone),但要確保每次治療時皆有部份組織不受能量影響,於是,每一個顯微加熱區的作用雖然強烈而明顯,但周圍都包覆著正常且結構完整的皮膚組織,使傷口能在短時間內癒合,並替換之前有缺陷的受損組織。Finescan不僅可讓表皮新生,更可促進深層膠原再生,從內而外徹底喚醒細胞,瞬時找回年輕時的肌膚狀態。憑藉最新的雙軸技術,FINESCAN 6可治療 – 面部 – 頸部 – 暗瘡凹凸洞 – 增生性疤痕

  27. I do believe all the ideas you have offered in your post. They are really convincing and can certainly work. Still, the posts are too brief for newbies. May you please prolong them a little from subsequent time? Thank you for the post.

  28. bursa evden eve nakliyat şirketimiz ev eşya taşıması yapılmadan önce müsterilerden randevu alınarak ev taşıması hakında bilgi verir. bursa evden eve nakliyat firmamız eleman ve eksper elemanları ile ev eşyalarının zarar görmemesi için ambalajlamasını kaliteli malzeme kullanarak yapar. Bu işlemlerden sonra ev esyalarınız guvenli bir şekilde nakil olur

  29. I wish to show some thanks to the writer just for rescuing me from this particular trouble. Just after surfing throughout the the web and obtaining thoughts which are not productive, I assumed my life was done. Living devoid of the solutions to the problems you’ve sorted out by means of your review is a crucial case, and those which may have badly damaged my career if I had not noticed your web page. Your main natural talent and kindness in maneuvering a lot of stuff was priceless. I don’t know what I would’ve done if I hadn’t come across such a solution like this. I can at this time look forward to my future. Thanks so much for your professional and effective guide. I will not be reluctant to propose your web blog to anyone who needs and wants care on this subject.

  30. I have two computers: I call one the “good” computer — it has two monitors. The other is my “junk” computer with one screen where I download a lot of stuff to it.. . If I wanted to continue using both computers but only with the dual monitors, what would I need to buy? Is there some sort of splitter I can buy that will allow me to switch between each CPU? Where can I buy one if it does in fact exist? Will I still be able to use one mouse and keyboard?.

  31. Hey there would you mind letting me know which hosting company you’re working with? I’ve loaded your blog in 3 completely different internet browsers and I must say this blog loads a lot quicker then most. Can you suggest a good hosting provider at a fair price? Thanks a lot, I appreciate it!

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>