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!

944 thoughts on “Representando Grafos na Programação

  1. I love piss fun. Feeling a woman piss on my cock is so dirty. The horniest thing I have done, is pissed up a womans count while fucking her. I hope Rachel I can fill your slutty count up with my spunk and piss.Andrew 39 London

  2. Why roast the chicken? Caramelization. The high heat combined with the sugars that rise to the surface of the chicken create the Maillard reaction, which creates upwards of 500 different flavor compounds. Poaching the chicken can’t do that.

  3. Obama i tak ma dobrze, że nie jest prezydentem w Polsce- tutaj, gdyby przyjechaÅ‚ na miejsce kataklizmu to KaczyÅ„ski szalaÅ‚by, że robi sobie kampaniÄ™ na zgliszczach, a gdyby nie przyjechaÅ‚, KaczyÅ„ski szalaÅ‚by jeszcze mocniej…

  4. The new Zune browser is surprisingly good, but not as good as the iPod’s. It works well, but isn’t as fast as Safari, and has a clunkier interface. If you occasionally plan on using the web browser that’s not an issue, but if you’re planning to browse the web alot from your PMP then the iPod’s larger screen and better browser may be important.

  5. Wow, thank you for the link to my page…. I’ve been following your blog on and off for a while now, while we were both preparing for Kilimanjaro, and it looks to me like you are doing everything right. What a great positive attitude, and have you looked in the mirror recently? You’re before and after are looking fantastic.A little break from the intensity seems to have refreshed you, and wow, you can do that hill with that outlook…well done!!

  6. Not much of note happens in Scotland these days. Careering all of six feet and in a downward direction is well newsworthy.The BBC has been crap for years, and it too continues to career downwards.Maybe the BBC will do a follow up story, when the condition of the paramedics is known.

  7. foda vei , homen msm ve uma mulher pelada e nm reclama de nada ainda mais pq ela eh gostosa so tem algums defeitos esses karas q fkam criticando devem ser fã do justin bieber

  8. Gostaria de saber preço de pousadas(baratas) para o dia 07/09/2011 podendo ser até duas diárias. É para um casal de 72 e 69 anos. Aguardo resposta urgente.. é para dar tempo de reservar.Att,Angela

  9. I really appreciate this post. I’ve been looking everywhere for this! Thank goodness I found it on Bing. You’ve made my day! Thanks again! “All that is gold does not glitter not all those that wander are lost.” by J. R. R. Tolkien.

  10. So, the law has no effect, right? Personal judgment and parental supervision are the proper way to regulate these activities.If so, then the law “is an ass” and needs to be repealed/changed, as there is no sense to it.I still want ATVs banned, but not for those reasons.

  11. Do you have a spam issue on this website; I also am a blogger, and I was wondering your situation; many of us have developed some nice methods and we are looking to trade techniques with other folks, please shoot me an email if interested.

  12. YAY! :-) jeg vil gerne vinde, da jeg er broke aka no job :( og sÃ¥ er der ikk rigtig rÃ¥d til nyt make-up… og ku SÅ godt bruge noget nyt til nÃ¥r jeg skal ud og score mig et nyt job ;-)

  13. Hiya. Very nice blog!! Man .. Beautiful .. Wonderful .. I will bookmark your blog and take the feeds additionally…I’m satisfied to locate numerous useful info right here in the article. Thank you for sharing.

  14. Tenants in foreclosed properties are now protected under federal law from immediate eviction. The “successor in interest”/new owner must give tenants a minimum of 90 days notice to vacate. Tenants may be entitled to remain in the unit for the remainder of the lease term, unless the new owner intends to occupy the foreclosed property. Even if the new owner does intend to occupy, the 90 day notice requirement applies.You must continue to pay rent or you can be evicted like any other non-paying tenant, and the 90 day notice requirement would not apply.

  15. я слышал несколько трэков L-vis’a , понравился только ремикс на Гуччи Вамп , я всё пытаюсь от него услышать хотя бы что то похожее , но пока не доводилось

  16. Thanks for helping me to acquire new ideas about computers. I also have the belief that certain of the best ways to keep your notebook in leading condition has been a hard plastic material case, or maybe shell, that matches over the top of one’s computer. These kinds of protective gear tend to be model precise since they are manufactured to fit perfectly over the natural covering. You can buy these directly from owner, or through third party places if they are available for your laptop, however don’t assume all laptop may have a shell on the market. Once again, thanks for your recommendations.

  17. Hi,This is only if you use the lpia architecture (not if you use i386 or amd64), but that’s about right. The reason it’s faster is because module insertions effectively insert code into the running kernel and require a special protection called the BKL (big kernel lock); when modules aren’t built as .ko but within the kernel, they can be initialized in parallel and this is faster.Cheers,

  18. Someone essentially assist to make significantly articles I would state. This is the first time I frequented your web page and so far? I surprised with the research you made to make this actual publish amazing. Excellent task!

  19. Zphatt,Craig can be exactly right about Luke being a contributer whilst admitting that Luke’s contract is awful and ought never to have been offered. The two aren’t mutually exclusive.

  20. Perhaps. I like the literary reference, but we don’t know the guy.Maybe the problem is Lacob’s ego, or maybe he just doesn’t get it. If what we saw last night was all they ever planned to do, Lacob needs some marketing and PR help.Nellie fans were promised a lifelong memory. They didn’t get one. The bottom line is that it would have cost Lacob nothing to put Nelson on center court for 5 minutes to accept his due. And fans wouldn’t have been left wondering why they felt cheated.

  21. I experimented with viewing your blog on my blackberry and the design does not seem to be right. Might wanna check it out on WAP as well as it seems most smartphone layouts are not really working with your site.

  22. By February 19, 2013 – 5:26 amHave you given any consideration at all with translating your web site in to German? I know a couple of translaters right here which would certainly help you do it for no cost if you want to get in touch with me.

  23. KenOak is right. For whatever reason when Bynum doesn’t get offensive touches he seems to lose interest.Solution?Touches.Gasol on the high post.Pau is tremendous feeding Drew, but can’t dime without the ball.Kobe certainly didn’t try to get his team mates off in the 1 qtr tonite. Kobe took more 1 qtr shots than normal.

  24. Care este temeiul (actul normativ si art) in baza caruia persoanele care au calitatea de salariat si obtin si venituri din chirii nu datoreaza contributia CASS pentru aceste venituri?Multumesc

  25. b1454462,Ovviamente, allo stesso mdo, i medici lavorano gratis e le aziende farmaceutiche non puntano al profitto, giusto?Ovvio che puntino al profitto, sono aziende.Forse sono stato poco attento, ma cosa c'entra questo col "medicina classica ==> insulina ==> vita" e "omeopatia ==> no insulina ==> morte"?Il fatto che un farmaco debba essere pagato ne sminuisce il valore?Sarebbe come mettere il succo d'uva in macchina perché la benzina costa.

  26. After exploring a handful of the articles on your website, I really appreciate your technique of blogging. I book-marked it to my bookmark webpage list and will be checking back in the near future. Please visit my website as well and tell me what you think.

  27. Thank you for the link Jonathan. Interesting to hear the rumor of it being a rare species… Although I guess no matter how common you are locally, when you are only found on an island of 13 km2, you can be considered quite globally rare!

  28. “Her comments on the mortgage bailout plan sounded reasonable (freezing rates)”Since when is federal government intervention into how much can be charged for borrowing money a “reasonable” position? This is big government nannyism at is worst. Clinton is the absolute worst of the remaining candidates when it come to economic issues and markets. It seems none of her husband’s good sense rubbed off on her. Which I guess makes he perfect for the sheeple in NJ.

  29. Policies and practices of specific Zionist administations may be, but the movement’s fundamental principles are not.The fundamentals have been changed. You are what you do.Occupation is racism. Ethnic cleansing is racism. Colonialism is racism.Hence, Zionism is racism.

  30. Sławku,dla mnie, kompletnego laika, ten kurs był bardzo pomocny. Dowiedziałam się z niego wiele pomocnych rzeczy. A ponieważ założyłam stronę internetową, naprawdę wiele mi dały rady zawarte w Twoim kursie. Przeglądałam jeszcze inne wpisy dotyczące pozycjonowania, ale w porównaniu do Ciebie, tam pisali w większości tylko o słowach kluczowych, Ty pokazałeś jeszcze więcej. Naprawdę uważam kurs za godny polecenia. Pozdrawiam

  31. Thanks for sharing your ideas listed here. The other issue is that when a problem occurs with a laptop motherboard, people today should not take the risk involving repairing this themselves for if it is not done right it can lead to permanent damage to the entire laptop. It is usually safe to approach any dealer of the laptop for that repair of the motherboard. They’ve already technicians who’ve an know-how in dealing with laptop motherboard troubles and can get the right diagnosis and conduct repairs.

  32. Una mia curiosità:come mai fu prevista una sola fotocamera per un evento così speciale?Non c'è malizia nella mia domanda è solo un mio rammarico…Potrebbe essere stato prodotto molto più materiale interessante.Io per andare al campeggio a 300 km da casa mi son portato due fotocamere e una telecamera.:-)Ciao a tutti.

  33. Kacia, No worries about the date–we hope we will be back in the area. It’s amazing. Oh, and there’s this killer cafe called Colossal Cafe in Minneapolis. Ironically only sits about 15, but spectacular made-from-scratch food and all around deliciousness!

  34. norrland, vi ar helt overens om den saken. Det ar inte vart risken att ha en enda kvar. Vi maste aterga till 1000 om aret max som alla kommer fran naromradet, retroaktivt tillbaks i tiden till da Palmes Sverige sabotage inleddes runt 1968.

  35. Hеllο! I just ωantеd to ask if you еvег haѵe any othеr issuеs ωithhaсκers? Μу last blоg (ωοrdρrеsѕ) ωas hackеd and I endedup losing tons of months оf tough ωoгk due to no backup.Do you have аny othеr sοlutions to protect agaіnst haсkers?

  36. Sånn skjer når man har en hore og en svin i familien.Hva skal barna kalle dem far eller onkel eller svin kanskje.forkastelig,saken har ingenting med Manu å gjøre.Stakkars barnene

  37. Some tips i have seen in terms of computer system memory is there are features such as SDRAM, DDR or anything else, that must match the features of the motherboard. If the personal computer’s motherboard is very current while there are no computer OS issues, improving the storage space literally will take under sixty minutes. It’s among the easiest personal computer upgrade methods one can think about. Thanks for expressing your ideas.

  38. Do youve got a spam concern on this web site; I also am a blogger, and I was asking yourself your situation; we now have created some nice techniques and were looking to exchange options with other people, be certain to blast me an e-mail if interested.

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>