Estruturas de Dados - Grafos

Olá caros alunos sejam bem-vindos a hora de hoje na hora de hoje nós falaremos sobre uma estrutura de dados muito importante que a estrutura de dados é chamada gráficos na hora de hoje eu vou seguir este roteiro primeiramente eu vou falar sobre aplicações dessa estrutura depois eu vou apresentar alguns conceitos básicos e por fim as formas de representação computacionais dessa estrutura primeiramente aplicações da estrutura as árvores vistas até agora mas são muito úteis para representar e hierarquias em que um o pai possui um ou mais nós filhos e quando precisamos remover a restrição de que

um filho pode ter apenas um pai uma expressão comum em árvore o poder de representação das Árvores acaba ficando insuficientes e um gráfico é capaz de representar esses casos então gráficos eles podem nos ajudar a representar o que cidades conectadas por estradas pessoas conectadas por relações de amizades páginas web conectadas por dia em que exato mais conectados por ligações químicas filmes conectados por preferência dos usuários animais conectados por relações ecológicas Estações conectadas por linhas de metrô e assim por diante essa essa lista Aí pode crescer indefinidamente eu consigo representar por gráficos basicamente tudo aquilo que

eu consigo pelo menos imaginar os conceitos básicos um gráfico g igual a ver é introduzir um gráfico G1 pavê é igual a veia é formado por esse par é uma estrutura formada por um conjunto ver onde é se vê o conjunto de vértice e aquilo esse conjunto estão identificando que vê possui n elementos e tão V = v1 V2 até VN e também o conjunto é de arestas onde cada aresta eu tô que eu tenho M arestas é um é dois até é m e cada uma dessas arestas por exemplo aresta é aí ela é

formada por um par de vértice pode ser por exemplo v1 V2 isso aqui é como se estivesse representando uma aresta e o gráfico ele pode ser edito direcionado ou não direcionar Vamos começar com gráfico não direcionado um gráfico será dito não direcionado se as relações apresentadas pelas arestas não tem sentido ou seja elas podem ser seguidas em qualquer direção sabemos então que o mar esta ela é um par de vips então quando nós descemos dizemos é e i.a. é igual a ver jdk é que eu estou colocando uma notação de conjunto ahn que eu quero

dizer o que que eu que essa área essa está dizendo que eu posso ir dvj até ver cá assim como ela pode dizer que eu estou indo de ver Cá até VJ onde vj-ii VK são vértices desse meu gato Ah e por outro lado um gráfico será direcionado se as arestas são pares ordenados de Beto lindo de um em direção ao outro em outras palavras Aqui eu estou dizendo que o i é igual a um par ordenado ver jdk que eu coloquei anotação de 40 indicando que por essa esta eu posso ir dvj que é

um verso ser chamado de origem até VK seria um verso ser chamado de origem onde VJ e VK pertencem ao conjunto de vértices desse meu gato e vamos agora falar sobre alguma nomenclatura que eu vou usar para uma certa frequência eu preciso que vocês entendam que eu estou falando basicamente é que eu vou falar sobre A nomenclatura do que é um grau em gráficos não direcionados o grau de um vértice é o número de arestas que incidem nele então por exemplo aqui eu tenho um vértice A e nesse vértice A incidem duas arestas essa esta

que tá ligando a com c e essa essa que está ligando a com B nesse caso como tem duas arestas incidentes em Ah eu digo que o grau de a = 2 da mesma forma o grau de c = 3 porque tem três arestas o grau de = 2 e o grau de de é igual a 1 e é gráficos não direcionados selfie looks não são permitidos o que que seria a selfie loop uma aresta saindo do SD bom e voltando para esse mesmo vértice de algo parecido com isso daqui no nesse gráfico direcionado Então

já deu para ver para gráficos direcionados esses selfie looks são permitidos Ele só não são permitidos para gráficos não direcionar Então vamos falar sobre os gráficos direcionado em grupos direcionados o grau é o número de arestas que saem do vértice também chamada de grau de saída e essas arestas são chamadas de arestas de saída mais onde a ser mais significa somado com o número de arestas que chegam ou seja o grau de entrada então vamos olhar para esse grafo direcionado que eu tenho desse lado direito aqui ele é muito semelhante a esse gráfico não direcionado

entre a tanto as arestas agora possuem certinhas dizendo que eu esse essa aresta aqui ela está ligando de a esse aqui é a origem até ser esse daqui é o destino então Aqui nós temos nesse nesse E aí cê tem duas arestas chegando são arestas de entrada então o grau de entrada seria igual a dois tem uma aresta saindo então grau de saída igual a 1 E qual seria o grau sem a soma desses dois valores então o grau desse vértice seria = 3 e o mesmo eu posso fazer para todos os outros vértices por

exemplo vértice A tem uma aresta de saída para ser e uma aresta de saída em direção a Bi Então ela tem duas arestas de saída não tem arestas de entrada então grau de entrada é igual a zero e o grau desse desse verso Então seria dois mais dentro q = 2 e quando tem esse céu looping que eu tenho aqui no grafo no vértice de nesse vértice deu até que nós temos nós temos uma aresta de entrada onde está estar esta de entrada essa essa aqui no céu filup ela está entrando no vértice a amar

esta de entrada ela tem duas arestas de saída que que é uma aresta de sair daqui a própria selfie looping por quê Porque o self louco está sendo contabilizado como uma aresta de entrada e uma aresta de saída ele foi contabilizado duas vezes mas essa aresta de saída bem aqui então qual é o grau de se veste se der aqui três por quê Porque tem as tarefas aqui de saída mais 10 aresta de sair daqui também que é o self loop mais aresta de entrada aqui também é o self lucro e vamos falar agora sobre

caminho o que que é um caminho um caminho entre dois vértices v-1 e v n é uma sequência de vértices e igual a V1 V2 até ver ele tal qvi e veio mais um ou seja dois pares nessa sequência pertencem à é ou seja são arestas para todo o intervalo de 1 a n - 1 então do primeiro até o penúltimo elemento já que penúltimo elemento pela nossa definição o penúltimo mais último já tem que ser uma festa então pegando aqui por exemplo eu quero linkar o vértice A até o vértice de qual seria um

caminho seria esse exemplo que eu estou colocando aqui de Ah até ser descer até é Edi é até de festa que seria um caminho porque serão caminho porque entre cada par tivesse na sequência existe em mar esta esse aqui é o k O Sapo Não direcionado no caso do grafo direcionado a gente tem que respeitar o sentido da aresta não poderia dizer que um caminho seria é cê a porque eu não posso dizer porque as arestas estão indicando outro caminho eu posso dizer que o ar por quê Porque existe uma aresta de até ser e

o mar esta de ser até esse daqui é um caminho contrário já não seria verdade as formas de representação tradicional mente um gráfico de representado o por uma matriz de adjacência ou Por uma coleção de lista de adjacência você pode inventar outra forma de representação entre a tanto essa daqui são padrão são canônicos na definição das representações vamos assumir que gráficos não são ponderados então quando eu for definir eu vou dizer aonde que ela fazer isso não são ponderados ou seja eles não possuem pesos nas arestas depois quando depois eu vou colocar algumas imagens e

nessas imagens eu mostro como seriam as definições para grafos ponderados e bom então vamos para as definições primeiramente com atrizes de adjacência só que eu vou definir o que é uma matriz de adjacência seja achei igual a ver é um gráfico com n vértices uma matriz de adjacências da vai ser uma matriz n-por-n talk with J vai ser igual a um Se houver uma aresta ainda do vértice ir para o bsj caso contrário eu vou dizer que o alho j.k. célula e j da Matriz tá vai ser igual a zero Então essa é a definição

de uma matriz de adjacência e uma definição de uma lista de adjacência uma lista de adjacências de um gráfico com n vértices consiste de um arranjo de n listas encadeadas é uma para cada vértice no Grau então cada vértice no gráfico vai ter uma lista encadeada e nesta lista encadeada eu coloco os adjacentes a esse tiver então para cada vértice uh a lista de adjacências de um contém todos os vizinhos de u no trato vamos verificar estas definições com alguns exemplos aqui em cima eu tenho um exemplo de um gráfico não direcionado e a matriz

de adjacência desse gráfico não direcionam então por exemplo a o ácido ideal seria o bebê isso quer dizer que na matriz de adjacência a célula AB EA se elas são iguais a um entretanto O alho também recebe como essa aqui é um gráfico não direcionado você e do bem eu também chego no A então por exemplo o Bea aqui também é um e do Ceará também é igual a um eu faço isso para todos os verbos por exemplo e eu posso chegar no leque Então esse que tá aqui está o dele e aqui está o

número 1 indicando aqui do de eu posso chegar no é como o gráfico é não direcionado essa essa Matriz de adjacência ela é triangular ela simétrica essa triângulo superior ele é igual a esse triângulo inferior então quando tem essa simetria é uma indicação de que esse gráfico é não direcionar e como seria uma listas de adjacência eu pegaria a todos os nós por exemplo só que iniciam as listas de adjacências coleções e dista de adjacências e do Noah Eu tenho dois vizinhos o beijos e então aqui eu tenho estadiamento de a para B e C

tá então esse ah tá ligando para o bebê para vocês são os vizinhos dele Ô Bia eu posso ir para o aí você então do B eu posso ir para o centro aqui na verdade não importa a ordem e dos e eu posso ir tanto para o ar quanto para o bebê quanto para o é essa que tá eu posso ir para lá para o bebê e para o em grafos direcionados a definição exatamente a mesma só que agora do a eu posso ir para o bebê e para você entretanto dos e eu já não

posso ir para o ar anteriormente tinha um aquilo sendo para o ar agora tem 10 por quê Porque agora as arestas elas possuem geração aí mas a definição é basicamente a mesma do deu posse pro Day aqui então não deu possa poder e do de eu posso ir para o é todo dia eu posso ir pro É nós até agora que essa Matriz aquela já não é simétrica esse triângulo superior e este triângulo inferior a um diferente e a representação e listas de adjacência assimila do ar eu posso ir para o bebê para você do

B eu posso apenas ir para você dos e eu posso ir apenas por é e do de eu posso ir pro é e poder sendo que é eu não posso ir para alugar nele bom então é isso que eu quero apresentar de uma trilha de assistência e lista de adjacência e se forem ponderados olha se forem ponderadas na matriz de adjacência basta trocar os valores em estado em um com o número um pelo peso por exemplo de a seu peso era algum então aqui está um de alfaber o peso era dois então coloca o dois

na matriz de B para a o peso era dois então que coloco dois aqui na matriz então é simplesmente pegar o valores que eram um e colocar o peso em lista de adjacência você vai ter que dar um jeito de colocar o peso dentro de alguma estrutura isso aqui é só uma representação para você saber a ligação de ar para bem Tem um peso dois a ligação de ar para ser tem o peso 1 de B para c tem o peso 3 e assim por diante você pode implementar isso aqui de várias e várias formas

e e agora de vantagens e desvantagens como atrizes de adjacência nós Voltaremos espaço para matriz inteira no momento da declaração da Matriz vamos imaginar as matrizes elas vão ter o mesmo problema dos vetores que a gente aprendeu em aulas anteriores quando nós alcançamos o vetor então não antes de usar o primeiro espaço do vetor nós temos que alocar em memória o vetor inteiro aqui a mesma coisa antes de usar o primeiro espaço na matriz você vai ter que colocar o espaço para Beatriz inteira e às vezes isso pode ocorrer antes de sabermos o número de

vértices e antes de sabermos o número de arestas Então você vai ter que fazer uma estimativa e essa estimativa torcer para ela ser a melhor possível se não Ou vai faltar o espaço Quando você quiser colocar mais velhas ou vai sobrar espaço demais bom então essa seria uma desvantagem aí dá uma crise adjacência você precisa fazer a locação a priori you É nesse segundo tópico aqui de vantagens e desvantagens aqui é uma desvantagem da Matriz de adjacência nesse segundo tópico se o grafo for denso ou seja tem muitas arestas em relação ao número de vértices

um gráfico com várias e várias arestas então a lista de adjacência ela acaba ocupando muito espaço em memória porque porque aquela coleção de listas de adjacência que Eu mencionei no slide anterior ela vai começar a ficar grande demais tão vai ter um nó esse novo acabar se ligando a vários e vários nós então cada uma dessas listas encadeadas vai ficar grande por outro lado as matrizes e adjacências ela ocupam o mesmo espaço Não importa o seu gráfico é espaço e não importa se o gráfico é denso por quê Porque você já colocou a matriz inteira

Então se o gráfico por dentro significa que vai ter muitos números um estão atriz seu braço por espaço significa que vai ter muitos números zero e na matriz Encantado a quantidade de espaço para guardar um é a mesma da quantidade de espaço para guardar o zero nesse caso se seu gráfico por denso é melhor dar uma certa preferência por utilizar uma crise de adjacência e as buscas em geral elas são melhores condições de adjacência pois a temos adjacentes de um LOL que que seria uma busca seria percorrer um caminho visitando os nós um dos Nós

pelo menos uma vez Vamos pensar no e percurso então elas vão ser melhores com listas de adjacência por quê Porque você está no nó e quer ir para o nosso vizinho uma lista de adjacência você já tem todos os adjacentes numa mesma estrutura de dados você não vai mais pesquisar precisar pesquisar como seria feito com as Matriz de adjacência você vai ter que ir lá e verificar é uma é uma aresta não é o mar esta não é uma aresta não e assim por diante e entretanto testar se existe uma aresta aresta entre dois vértices

estado se nesses desse vértice é melhor com uma crise adjacência por quê Porque basta ir lá na matriz verificar se o número que está na matriz e 01 e acessaram o número da Matriz pode ser feito em tempo constantes então testar se existe uma aresta dado que você já sabe o índice dos vértices que você quer testar pode ser feito em tempo constante melhor do que com uma lista de adjacência que você teria que procurar sequencialmente por todos os adjacentes é um nó na lista a encontrar os predecessores de um nó é melhor com matrizes

de adjacência porque porque se você quer encontrar os predecessores de um nó você olha na coluna perspectiva daquele nova tá você não hora nadinha porque porque nadinha você vai ver de um para onde você pode ir a partir daquele nó e nas colunas você pode ver de onde você pode vir para chegar naquele inox são os predecessores bom E no caso se estivéssemos implementando utilizando listas de adjacência nós prestaremos basicamente Barreto todas as listas de adjacência para que para verificar se de um dado elemento eu posso chegar no elemento onde eu quero chegar que seria

o elemento onde eu estou de quem estou computando todos os predecessores bom então basicamente as formas de representação elas vão interferem muito em como o seu algoritmo vai se comportar em na questão de tempo processamento eficiência de processamento e também na questão de espaço que vai ser ocupado aqui eu mostro algumas vantagens e desvantagens que guiam aí você o na hora de desenvolver a tomar essa essa decisão entretanto Cabe a você tomar decisão não vou dizer olha a uma uma forma de apresentação é melhor do que a outra não cada caso é um caso Então

você decide baseado nesses critérios em alguns outros critérios dependendo da sua aplicação é para isso que eu tenho para dizer nessa aula de hoje foi a primeira introdução à estrutura de dados escravos na próxima aula eu falo um pouco sobre a implementação dessa estrutura de dados gráficos usando matrizes de adjacência novamente se você não entendeu o algo da aula eu recomendo que assista o vídeo novamente caso contrário encontro você na próxima aula de implementação um forte abraço e até a próxima um E aí E aí [Música]