Conteúdo principal
Curso: Computer science theory > Unidade 1
Lição 10: Representação do grafoRepresentando grafos
Existem muitas maneiras de se representar gráficos, cada uma com suas vantagens e desvantagens. Algumas situações ou algoritmos nos quais queremos usar gráficos como entradas pedem por uma representação, e outros pedem outra diferente. Aqui, veremos três maneiras de representar gráficos.
Vamos examinar três critérios. Um deles é a quantidade de memória, ou espaço, precisamos em cada representação. Vamos usar notação assintótica para isso. Sim, podemos usar notação assintótica para outros fins além de expressar tempos de execução! Na verdade, ela é uma forma de caracterizar funções, e uma função pode descrever um tempo de execução, uma quantidade de espaço necessário ou algum outro recurso. Os outros critérios que vamos usar se relacionam com o tempo. Um é quanto tempo leva para determinar se uma dada aresta faz parte do gráfico. O outro é quanto tempo leva para encontrar os vizinhos de um dado vértice.
É comum identificar os vértices não pelo nome (como "Andreia", "Boston" ou "suéter") mas sim por um número. Ou seja, tipicamente numeramos os vértices de 0 até . Aqui está o gráfico da rede social com seus 10 vértices identificados por números e não por nomes:
Listas de arestas
Um modo simples de representar um gráfico é simplesmente como uma lista, ou arranjo, de arestas, que chamamos de lista de arestas. Para representar uma aresta, temos simplesmente um arranjo de dois números de vértice, ou um arranjo de objetos que contém os números dos vértices sobre os quais as arestas são incidentes. Se as arestas tiverem pesos, adicione um terceiro elemento ao arranjo ou mais informações sobre o objeto, fornecendo o peso da aresta. Como cada aresta contém apenas dois ou três números, o espaço total para uma lista de arestas é . Por exemplo, é assim que representamos uma lista de arestas do gráfico da rede social em JavaScript:
[ [0,1], [0,6], [0,8], [1,4], [1,6], [1,9], [2,4], [2,6], [3,4], [3,5], [3,8], [4,5], [4,9], [7,8], [7,9] ]
Listas de arestas são simples, mas se quisermos descobrir se o gráfico contém uma aresta em particular, precisamos procurá-la na lista de arestas. Se as arestas aparecerem na lista sem uma ordem particular, teremos que conduzir uma busca linear por arestas. Aqui está algo para pensar: como você pode organizar uma lista de arestas de forma a fazer com que a busca por uma aresta em particular leve o tempo ? A resposta é um pouco complicada.
Matrizes de adjacência
A matriz de adjacência de um gráfico com vértices é uma matriz de 0s e 1s, na qual a entrada na linha e coluna é 1 se e somente se a aresta estiver no gráfico. Se você quiser indicar o peso da aresta, coloque-o na entrada da linha , coluna , e reserve um valor especial (talvez
vazio
) para indicar uma aresta ausente. Esta é a matriz de adjacência para o gráfico da rede social:Em JavaScript, representamos a matriz por:
[ [0, 1, 0, 0, 0, 0, 1, 0, 1, 0],
[1, 0, 0, 0, 1, 0, 1, 0, 0, 1],
[0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 1, 1, 0, 0, 1, 0],
[0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
[0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
[1, 0, 0, 1, 0, 0, 0, 1, 0, 0],
[0, 1, 0, 0, 1, 0, 0, 1, 0, 0] ]
Com uma matriz de adjacência, podemos descobrir se uma aresta está presente em um tempo constante, ou simplesmente procurando pela entrada correspondente na matriz. Por exemplo, se a matriz de adjacência for chamada está no gráfico examinando de espaço, mesmo se o gráfico for esparso: com relativamente poucas arestas. Em outras palavras, a matriz de adjacência de um gráfico esparso é composta principalmente por 0s, e usamos muito espaço para representar apenas algumas poucas arestas. Segundo, se você quer achar qual vértice é adjacente para um dado vértice , você tem que olhar para todas as entradas na coluna , mesmo se um pequeno número de vértices são adjacentes ao vértice .
graph
, então podemos pesquisar se a aresta graph[i][j]
. Então, qual é a desvantagem de uma matriz de adjacência? Duas coisas, na verdade. Primeiro, ela ocupa A matriz de adjacência de um gráfico não direcionado é simétrica: a entrada da linha , coluna é 1 se e somente se a entrada da linha , coluna for 1. A matriz de adjacência de um gráfico direcionado não precisa ser simétrica.
Listas de adjacência
A representação de um gráfico com listas de adjacência combina as matrizes de adjacência com as listas de arestas. Armazene um arranjo dos vértices adjacentes a cada vértice . Tipicamente, temos um arranjo de listas de adjacência, uma lista por vértice. Aqui está uma representação do gráfico da rede social em forma de lista de adjacência:
Em JavaScript, representamos essas listas de adjacência por:
[ [1, 6, 8],
[0, 4, 6, 9],
[4, 6],
[4, 5, 8],
[1, 2, 3, 5, 9],
[3, 4],
[0, 1, 2],
[8, 9],
[0, 3, 7],
[1, 4, 7] ]
Os números de vértice em uma lista de adjacência não precisam aparecer em nenhuma ordem em particular, embora muitas vezes seja conveniente listá-los em ordem crescente, como neste exemplo.
Podemos chegar à lista de adjacência de cada vértice em um tempo constante, porque precisamos apenas indexar em um arranjo. Para descobrir se uma aresta está presente no gráfico, vamos à lista de adjacência de em tempo constante e então procuramos por na lista de adjacência de . Quanto tempo isso leva, no pior caso? A resposta é , onde é o grau do vértice , porque esse é o tamanho da lista de adjacência de . O grau do vértice pode chegar, no máximo, a (se for adjacente a todos os outros vértices) ou, no mínimo, a 0 (se estiver isolado, sem arestas incidentes). Em um gráfico não direcionado, o vértice está na lista de adjacência de se e somente se estiver na lista de adjacência de . Se o gráfico for pesado, então cada item em cada lista de adjacência é ou um arranjo com dois itens ou um objeto, que fornece o número do vértice e o peso da aresta.
Você pode usar um laço for para percorrer os vértices em uma lista de adjacência. Por exemplo, suponha que você tem a representação de um gráfico em forma de lista de adjacência na variável . Então, para chamar , você pode usar o seguinte código JavaScript:
graph
, de forma que graph[i]
seja um arranjo que contém os vizinhos do vértice doStuff
em cada vértice adjacente ao vértice for (var j = 0; j < graph[i].length; j++) {
doStuff(graph[i][j]);
}
Se a notação com subscrito duplo o confundir, você pode pensar nela dessa forma:
var vertex = graph[i];
for (var j = 0; j < vertex.length; j++) {
doStuff(vertex[j]);
}
Quanto espaço a lista de adjacência ocupa? Temos listas, e embora cada lista possa ter pelo menos vértices, no total a lista de adjacência de um grafo não direcionado contém elementos. Por que ? Cada aresta aparece exatamente duas vezes nas listas de adjacência, uma na lista de e uma na lista de , e há arestas. A lista de adjacência de um grafo direcionado contém um total de elementos, um por aresta direcionada.
Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.
Quer participar da conversa?
Nenhuma postagem por enquanto.