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’d need to test with you here. Which is not one thing I normally do! I get pleasure from studying a put up that may make people think. Additionally, thanks for permitting me to remark!

  2. What i do not realize is actually how you’re not really much more well-liked than you may be right now. You’re so intelligent. You realize thus significantly relating to this subject, made me personally consider it from a lot of varied angles. Its like women and men aren’t fascinated unless it’s one thing to do with Lady gaga! Your own stuffs great. Always maintain it up!

  3. I’ve been surfing on-line greater than three hours nowadays, yet I by no means discovered any interesting article like yours. It is beautiful price enough for me. Personally, if all site owners and bloggers made just right content material as you did, the internet shall be a lot more useful than ever before. “No one has the right to destroy another person’s belief by demanding empirical evidence.” by Ann Landers.

  4. I simply wanted to compose a quick word to be able to say thanks to you for those marvelous secrets you are showing at this website. My extended internet research has at the end of the day been recognized with sensible tips to talk about with my guests. I ‘d believe that we site visitors actually are very lucky to dwell in a magnificent website with many wonderful individuals with valuable techniques. I feel very much blessed to have discovered the webpage and look forward to so many more thrilling minutes reading here. Thanks once again for all the details.

  5. Simply wanna input on few general things, The website pattern is perfect, the content material is rattling good. “We can only learn to love by loving.” by Iris Murdoch.

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

  7. Valuable info. Lucky me I found your web site by accident, and I am shocked why this accident didn’t happened earlier! I bookmarked it.

  8. Incredible! This blog looks exactly like my old one! It’s on a completely different topic but it has pretty
    much the same page layout and design. Great choice of colors!

  9. Thanks for ones marvelous posting! I actually enjoyed reading it, you could be a great author.I will make sure to bookmark your blog and will eventually come back very soon. I want to encourage you continue your great posts, have a nice evening!

  10. I want to express thanks to this writer just for rescuing me from such a scenario. Right after browsing through the world wide web and seeing tips which were not powerful, I believed my life was over. Being alive without the presence of answers to the problems you have solved by way of your good write-up is a crucial case, and the ones which might have badly affected my entire career if I had not come across your web site. Your actual expertise and kindness in controlling all the things was crucial. I am not sure what I would have done if I hadn’t encountered such a stuff like this. It’s possible to now look forward to my future. Thanks a lot so much for your specialized and sensible guide. I will not be reluctant to endorse your web site to anybody who will need tips about this issue.

  11. I will right away take hold of your rss as I can not find your email subscription hyperlink or newsletter service. Do you have any? Please permit me recognize so that I may just subscribe. Thanks.

  12. Hi there! I just wanted to ask if you ever have any issues with hackers? My last blog (wordpress) was hacked and I ended up losing many months of hard work due to no back up. Do you have any methods to protect against hackers?

  13. Sick and tired of being bored? There’s nothing at all good to watch on TV these days. How many cat videos can you watch at YouTube? What you really want is some live adult entertainment. That’s what http://www.camgirl.pw is all about. It’s 24/7 excitement like you’ve never seen before. Check it out and tell a friend. Something this good needs to be shared.

  14. Great website. Lots of useful info here. I’m sending it sex a few buddies ans additionally sharing in delicious. And naturally, thanks for your effort!

  15. It is one of the automobile industry’s most widely issued global set of standards for quality management, ISO/TS 16949. Its evolving with the publication of a new world wide industry set of standards brought to us by the International Automotive Task Force (IATF). This recent edition was developed with an unprecedented response from industry feedback and direct engagement from AIAG associates representing North America.

  16. My husband and i have been quite delighted that Michael could conclude his studies because of the ideas he received when using the web page. It’s not at all simplistic just to continually be releasing concepts which usually most people may have been selling. We acknowledge we have got the blog owner to appreciate for this. The illustrations you made, the straightforward web site navigation, the relationships your site help promote – it’s got mostly spectacular, and it is aiding our son and our family reckon that this topic is brilliant, and that is seriously vital. Thanks for all the pieces!

  17. My husband and i felt really peaceful that Peter could finish off his researching while using the ideas he gained from your web pages. It is now and again perplexing to simply possibly be releasing thoughts that many others could have been selling. We see we have got the writer to appreciate because of that. The type of explanations you made, the easy blog menu, the relationships you will make it possible to foster – it’s everything exceptional, and it’s really leading our son in addition to the family understand that subject matter is brilliant, and that’s really mandatory. Thank you for all the pieces!

  18. Informasi yang disediakan dalam tulisan ini seharusnya mencerahkan kalian seputar situasi sulit websiteging. Apabila kalian benar-benar memanfaatkan alat seperti websiteging maka anda dapat menjadi berhasil di banyak bidang, seperti mempromosikan bisnis atau produk. bloggingging dapat membuka banyak pintu untuk anda, jadi pertimbangkan untuk mengaplikasikannya dengan efek yang bagus.

  19. Jikalau anda tertarik untuk membuat pengikut setia untuk blogging kalian, pilih topik yang kamu minati dan kenal banyak. Kemudian berpegang pada topik itu untuk beberapa besar. Kalau kalian terus menawarkan konten yang berkaitan dengan topik atau tema tertentu, pembaca akan terus datang kembali untuk mencari isu baru.

  20. When I initially commented I clicked the -Notify me when new feedback are added- checkbox and now every time a comment is added I get four emails with the same comment. Is there any method you possibly can remove me from that service? Thanks!

  21. My spouse and i got so excited Ervin could complete his researching from your precious recommendations he had in your weblog. It’s not at all simplistic to just find yourself giving for free steps that the others may have been trying to sell. And we also fully understand we have you to give thanks to for that. The most important illustrations you’ve made, the simple website navigation, the relationships you can give support to promote – it’s got mostly astounding, and it’s making our son in addition to the family reason why the idea is brilliant, which is certainly tremendously essential. Thanks for all!

  22. Good Info Buddy. It Helps a lot. Love to see you posts. Our Indian Escorts in Hyderabad are very discrete, honest and professional with client. Our Escort girls offer in call and outcall services in every major area in Hyderabad. Our most trusted Indian Escorts having great intelligence, humour and charm to seduce the clients. They’ll make surely your remain in Hyderabad will become ne’er -to-be-forgot. In become the escort agency Hyderabad-Love insures that everybody is covered discreet, professional and anonymous. Contact Miss Anjali @ http://www.missanjali.com

  23. Hi there would you mind sharing which blog platform you’re using? I’m going to start my own blog soon but I’m having a difficult time selecting between BlogEngine/Wordpress/B2evolution and Drupal. The reason I ask is because your design and style seems different then most blogs and I’m looking for something unique. P.S Sorry for getting off-topic but I had to ask!

  24. Hey there would you mind sharing which blog platform you’re using?
    I’m looking to start my own blog in the near future but I’m having a tough time
    deciding between BlogEngine/Wordpress/B2evolution and Drupal.

    The reason I ask is because your layout seems different then most blogs and I’m looking for something completely unique.
    P.S My apologies for being off-topic but I had to ask!

  25. My brother suggested I would possibly like
    this web site. He used to be totally right. This put up truly
    made my day. You cann’t consider just how a lot time I had spent for this information! Thank you!

  26. Oh my goodness! Impressive article dude! Thank you, However I am encountering
    difficulties with your RSS. I don’t know the reason why I am
    unable to join it. Is there anybody getting the
    same RSS issues? Anyone that knows the solution can you kindly respond?

    Thanx!!

  27. Having read this I believed it was rather enlightening. I appreciate you finding the
    time and effort to put this content together. I once
    again find myself personally spending a lot of time both reading and leaving comments.

    But so what, it was still worthwhile!

  28. Hello there, I discovered your website via Google whilst searching for a comparable topic, your site came up,
    it seems to be great. I’ve bookmarked it in my google bookmarks.

    Hello there, simply become alert to your weblog through Google, and found that it
    is truly informative. I am gonna be careful for brussels.
    I’ll be grateful in case you proceed this in future.
    Lots of folks can be benefited from your writing. Cheers!

  29. I in addition to my buddies have already been checking the great points found on your website and then instantly I had an awful feeling I had not thanked the web blog owner for those strategies. All of the women are actually for this reason excited to see them and already have surely been loving them. Many thanks for truly being very kind and then for considering these kinds of fabulous subject matter most people are really desirous to learn about. My very own honest apologies for not expressing gratitude to you sooner.

  30. Good Info Buddy. It Helps a lot. Love to see you posts. Our Indian Escorts in Hyderabad are very discrete, honest and professional with client. Our Escort girls offer in call and outcall services in every major area in Hyderabad. Our most trusted Indian Escorts having great intelligence, humour and charm to seduce the clients. They’ll make surely your remain in Hyderabad will become ne’er -to-be-forgot. In become the escort agency Hyderabad-Love insures that everybody is covered discreet, professional and anonymous. Contact Miss Anjali @ http://www.missanjali.com

  31. Hello there! This is my first visit to your blog! We are a group of volunteers and starting a new project in a community in the same niche. Your blog provided us valuable information to work on. You have done a wonderful job!

  32. I would like to thnkx for the efforts you have put in writing this blog. I am hoping the same high-grade blog post from you in the upcoming also. In fact your creative writing abilities has inspired me to get my own website now. Really the blogging is spreading its wings fast. Your write up is a good example of 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>