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,249 thoughts on “Representando Grafos na Programação

  1. I am late to the party here, but just wanted to say thanks for this:“When editing the page, go to the screen options in the upper right. Make sure revisions is checked. Once it is you should see the revisions box in the page below. ~Tanya”That saved my life. I have been using WordPress for YEARS and had no idea that menu was at the top.Thanks again, Ryabn

  2. PHP SEO: Search Engine Optimization
    php seo uzmanı olarak şirketimiz php seo hizmeti vermektedir günümüz ortamında site sahiplerinin php bilgisi nekadar iyi olsada php seo metotları arama motorlarında optimize edilmesi gereken hususlardan bir tanesi web siteniz nekadar iyi olsada arama motorlarına duyarlı olmasına özen gösterin. php seo uzmanlarımızdan destek alabilirsiniz.

  3. I don't understand Perry's comments to be advocating a solution for the gender gap but rather a figurative head scratching due to the fact that the treatment of men's overall deficiency versus the treatment of women's engineering deficiency are so different. a head scratching bemusement I've grown to share.

  4. My brother recommended I may like this blog. He was totally right.

    This publish truly made my day. You cann’t imagine simply how a
    lot time I had spent for this information! Thanks!

  5. …I swear you just can't trust anything anymore in A-merry-ca. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Nope! You sure can't! or in it's possessions/colonies. This morning three doctors and a bunch of pharmacists and pharmacy owners,33 persons in all, were arrested for writing prescriptions of controlled pills for phony patients and filling them to be sold on the street. I don't know how many of the pharmacist are actually guilty or just innocent employees but they were all arrested. Although I don't understand because the pharmacies and labs are making as much as the doctors what with all the sick people around!

  6. I do not fully understand it) Youtube promotion of high production value and grass roots series/shows would be a major way for youtube to start matching the revenue of other video websites like hulu. Just think of youtube as an independent cable channel that looks for viewable content that will keep on running.

  7. Ihj altså, endnu en vildt lækker adventskonkurrence Ørenringene er bare for smukke!! Ville style dem med en lang sort kjole, stilletter, og lange bølgede krøller opsat, så man self. kan se disse bedårende ørenringe. Og til sidst et par røde læber.

  8. I believe Donavan has earned the right to retire on his own terms. He has done so much for U.S. Soccer and MLS and has left it all on the field. He has taken criticism (some deserved) and proven many skeptics wrong. Many fans felt he did not fulfill his potential ( I was one of them), but in retrospect, I think he provided U.S. Soccer and MLS exactly what was needed: a American soccer star.

  9. You made some respectable factors there. I seemed on the web for the difficulty and located most individuals will associate with together with your website.

  10. Pretty component of content. I just stumbled upon your website and in accession capital to say that I get actually loved account your weblog posts. Any way I’ll be subscribing in your augment and even I success you access persistently rapidly.

  11. 我們採用國際及美國食品及藥物管理局FDA認可的CO2 激光儀 LUTRONICS® SPECTRA SPR, 具安全性, 準確度高 . 二氧化碳激光可安全地去除皮膚上的癦痣、肉粒、疣、老人斑等問題。此激光的幼細光束可準確及直接地將要去除的組織氧化,過程快捷,傷口細小及乾淨,對周圍的皮膚傷害減至最少。一般1-2次就可永久去除。

  12. Cartoonland-Gast 3  3“Die meisten Menschen in diesem Video sind dem Tod noch einmal von der Schippe gesprungen….” Genau: “die meisten”, aber eben nicht alle. Deshalb gehört das Video nicht auf eine Fun-Site, sorry…

  13. Woah! I’m really loving the template/theme of this site. It’s simple, yet effective. A lot of times it’s very difficult to get that “perfect balance” between superb usability and visual appeal. I must say that you’ve done a great job with this. Additionally, the blog loads very fast for me on Opera. Excellent Blog!

  14. Yo fui uno de esos bloggeros, poeta maldito que se enamoró de una Musa, pero la distancia (donde se funde el sueño),acaba por estropearlo todo.Yo tambien fui una víctima del amor que murió en una tumba digital, maté mi blog, mi vida y mi sueño, pero sigue el poeta, esta vez no buscando musas de internet.Precioso blog Mal de amores y gracias por leerme cuando tenía el mío!

  15. A formidable share, I simply given this onto a colleague who was doing a bit of analysis on this. And he in reality purchased me breakfast as a result of I found it for him.. smile. So let me reword that: Thnx for the treat! But yeah Thnkx for spending the time to discuss this, I really feel strongly about it and love reading extra on this topic. If possible, as you develop into expertise, would you thoughts updating your weblog with more particulars? It’s highly helpful for me. Large thumb up for this weblog submit!

  16. I’ve never had to pull over, and perhaps I should have because I cried one of my contacts right into my lap. Gee, that’s nice doing 60 on the freeway. This past Sunday I saw three teenaged boys at the altar during worship, jumping around, hands in the air on over their hearts. Needless to say there was a major mascara incident.

  17. school girls porn sex 3gp free download,3gp bhabi sex video free
    download, desi xxx video, katrina kaif sex 3gp download, www free
    mobile 3gp andan xxxsexy videos.com,Download indian xxx, PAkistani sex in 3gp, Indian xxx.
    Indian 3gp porn videos, Pakistani sex vidoes download.com, hot indian porn downlod, free dawnlaod sex video,
    paki sex clip dwnld, xxx 3gp Indian sex video,
    lndian sex dounload, free dounload sex video, porn 3gp dowland, xxx indian sex 3gp,,
    free sex ienda 3gp mp4 video dawnload, free sex video
    download, Best xxx video 3gp, indian xxx prone 3gp,
    xxx.dawnlod.india, xxx ind school, pakistani xxx video download hd, porn india vidio downlod com.,
    http://www.xxx sex video.com free downlod, free download xxx video.

    Download Sex Videos, Indian xxx 3gp videos, Hot Sex, mp4 sex videos, Sex
    movie 3gp, Indian, Aunty, Bhabi, Mom son, School girl, teacher student,
    sister sex,bhabi sex, animal sex, young girl rape, indian lesbian anal tamil arab group sex blowjob scandal mms big boobs sex Mms SexIndian Porn scandal
    Sex Bhabi desi Sex Aunty Sex Rape Sex school mms Desi Chudai Sex dawnload indian fuk movie xxx videos dowload xxx free download xxx videos online bigg boobs sex.

  18. I love that when the power went out, y’all went out for beers! I just bought the Blue Moon Pumpkin and it’s pretty darn good. I’d love to find one that has more spice to it if you have any suggestions! As far as spinach goes….I’m not much help, I use it in smoothies, salads or just toss it in whatever I happen to be cooking!

  19. “We need to get cheap, kid-friendly comics into venues where kids can find them and buy them”They are. Marvel and DC both produce Marvel Adventures and Johnny DC respectivley that are aimed at younger kids. Plus Disney still produces comics like Ducktales, Bongo puts out Simpsons Comics, and Stan Sakai’s Usagi Yojimbo has always been accesible for all readers.But seeing as how the majority of comic book readers are adults, comics are written for adults.

  20. I simply wanted to compose a message in order to thank you for the fantastic ways you are sharing here. My time intensive internet research has at the end of the day been honored with useful details to go over with my companions. I ‘d express that most of us site visitors actually are quite lucky to dwell in a fine site with very many perfect professionals with helpful basics. I feel rather privileged to have encountered your entire site and look forward to plenty of more thrilling moments reading here. Thanks again for a lot of things.

  21. Nice post. I learn one thing more challenging on totally different blogs everyday. It is going to at all times be stimulating to read content material from other writers and practice a little bit one thing from their store. I抎 favor to use some with the content on my weblog whether you don抰 mind. Natually I抣l provide you with a link on your internet blog. Thanks for sharing.

  22. I am also writing to let you know what a notable experience my wife’s princess found using your site. She noticed many issues, including what it is like to possess an incredible giving style to make the rest with ease master a number of tortuous subject areas. You really did more than readers’ desires. I appreciate you for supplying the helpful, safe, educational as well as cool guidance on your topic to Jane.

  23. AJ’s photos certainly make this a tempting restaurant but Greek inspired foods can be an acquired taste. It definitely has a different flavor profile than I would ordinarily care for. I did enjoy many meals at Spoodles and feel nostalgic thinking about it. If I can hypnotize my picky eater I will give Kouzzina a try on our next visit.It’s too bad the beers are in green bottles, a major cause of skunkiness.

  24. Tak samo jest w Polsce z PIS. Niby starajÄ… siÄ™ być partiÄ… umiarkowanÄ… „demokratycznÄ…” cokolwiek to u nich oznacza, ale od czasu do czasu robiÄ… wstawki o charakterze skrajnym, nawet narodowo-socjalistycznym. I od razu tracÄ… kilka pkt u wyborców a od 2005 roku nie wybgrali żadnych wyborów. Roomeny miaÅ‚ przykÅ‚ad jak NIE nalezy robić. ByÅ‚ nawet w Polsce, ale jako Amerykanin zawsze wie lepiej no i… miaÅ‚o być jak nigdy a wyszÅ‚o jak zawsze.

  25. It’s best to take part in a contest for probably the greatest blogs on the web. I’ll recommend this web site!

  26. I am not sure where you’re getting your information, nevertheless vast issue. I desires to spend approximately schedule erudition much more otherwise understanding more. Recognition for vast in sequence I was looking in support of this information for my mission.

  27. [..YouTube..] Great Video !!!!!!!! Great conversation, Its about time that we get our STOMP on? You ready. TO GET YOUR STOMP ON???? I know that 444 seamed a little disappointing to you, BUT that said 555 has something to say about it. We all slide,we all slip we all expect more than we should of ourselves GOD MADE HUMANS HE DID NOT MAKE US GODS if he did we would not have this community. We are real people FIGHTING A REAL FIGHT. you are focused , working hard and you will see what you want to C ctrygirl555

  28. I remember when I was about 4 years old, someone mentioned that taxes were voluntary. Even at that age, my first thought was “why would anyone pay them?” and my second thought was, “I’m not gonna pay them.” Obviously, they lied to me.To this day, I think that all taxes should be voluntary and that all government services should have to compete with private alternatives. If there is a government service for which no private alternatives exist, that’s a damned good indication that the government shouldn’t be doing it in the first place.  Robert Bruce Thompson

  29. Eu só queria dizer que me parece correcto o uso da palavra "longitude", porque ali não é simplesmente a lonjura que conta. Ali o que conta, além da distância a vencer, o que conta é a altitude e a atitude. Logo a atitude de vencer a distância para chegar à Senhora em tal altitude é a longitude. Parece-me claro.

  30. ankara deha nakliyat firmansı. ankara evden eve nakliyat ev ofis taşımacılığı, şehiriçi şehirler arası nakliyat, eşya depolana hizmetlerini kusursuz olarak uzman kadromuzla 7/24 hizmetimizdeyiz ankara deha nakliyat firması…

  31. IELLIOS是由歐盟資助倫敦大學細胞重建研究所研究. 採用諾貝爾生理醫學獎科技 , 透過”納米能量電流” 以最親膚與迅速導入的方式 , 利用電腦化系統去令皮膚再生 , 令皮膚組織在無創傷的情況下自然更新及收緊 . 這治療是無創無痛的 . 完成治療後亦沒有傷口 . 我們是香港第一引入IELLIOS的機構 , 醫生會根據客人不同情況去為你設計不同的組合 .在外國IELLIOS受到很多荷里活明星, 歌手以至政客的追棒 , Madonna的facialist kate somer -field就常用IELLIOS為她護理肌膚 , 令52歲的她肌膚輪廓均保持於30歲的狀態. IELLIOS的訊號技術,採用心臟起博起原理,活躍無法正常運作的心臟細胞。訊號技術可活化及修復愛損皮膚,透過傳送訊號,激活靜止的細胞。IELLIOS的訊號技術給予細胞指令,引發細胞再次生長,令肌膚重回年輕。

  32. `I THOUGHT I TOLD YOU TO SHUT YOUR PIEHOLE, OBOT!´oooh! get a load of her!you don´t have the right to tell me what to do you inbred stumpfucker. just read the text above the comments box hypocrate! or do you wish to suppress opposing opinions just like a nice little communist?as for oily, she can sue me if she wants. she´d probably screw that up as well and i´d end up getting a nice slice of cash.

  33. Youre so cool! I dont suppose Ive read something like this before. So good to seek out anyone with some original thoughts on this subject. realy thanks for beginning this up. this web site is something that is wanted on the internet, someone with a bit of originality. useful job for bringing something new to the web!

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

  35. Thanks Ian,Even more important things that were NOT described by Mess'rs Palmer and Till.Did they come up on the Ledgie Boy Broadcast?I ask because I noted that Mr. Baldrey was also trashing the NDP on the Twittmobile .

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>