Conteúdo principal

Curso: Computer science theory > Unidade 1

Lição 10: Representação do grafo

Representando 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

| V |

de 0 até

| V | - 1

. 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

| E |

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 é

Θ (E)

. 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

| E |

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

O (\lg E)

? A resposta é um pouco complicada.

Matrizes de adjacência

A matriz de adjacência de um gráfico com

| V |

vértices é uma matriz

| V | \times | V |

de 0s e 1s, na qual a entrada na linha

i

e coluna

j

é 1 se e somente se a aresta

(i, j)

estiver no gráfico. Se você quiser indicar o peso da aresta, coloque-o na entrada da linha

i

, coluna

j

, 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 graph, então podemos pesquisar se a aresta

(i, j)

está no gráfico examinando graph[i][j]. Então, qual é a desvantagem de uma matriz de adjacência? Duas coisas, na verdade. Primeiro, ela ocupa

Θ (V^{2})

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

i

, você tem que olhar para todas as entradas

| V |

na coluna

i

, mesmo se um pequeno número de vértices são adjacentes ao vértice

i

A matriz de adjacência de um gráfico não direcionado é simétrica: a entrada da linha

i

, coluna

j

é 1 se e somente se a entrada da linha

j

, coluna

i

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

i

. Tipicamente, temos um arranjo de

| V |

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

(i, j)

está presente no gráfico, vamos à lista de adjacência de

i

em tempo constante e então procuramos por

j

na lista de adjacência de

i

. Quanto tempo isso leva, no pior caso? A resposta é

Θ (d)

, onde

d

é o grau do vértice

i

, porque esse é o tamanho da lista de adjacência de

i

. O grau do vértice

i

pode chegar, no máximo, a

| V | - 1

(se

i

for adjacente a todos os outros

| V | - 1

vértices) ou, no mínimo, a 0 (se

i

estiver isolado, sem arestas incidentes). Em um gráfico não direcionado, o vértice

j

está na lista de adjacência de

i

se e somente se

i

estiver na lista de adjacência de

j

. 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 graph, de forma que graph[i] seja um arranjo que contém os vizinhos do vértice

i

. Então, para chamar doStuff em cada vértice adjacente ao vértice

i

, você pode usar o seguinte código JavaScript:

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

| V |

listas, e embora cada lista possa ter pelo menos

| V | - 1

vértices, no total a lista de adjacência de um grafo não direcionado contém

2 | E |

elementos. Por que

2 | E |

? Cada aresta

(i, j)

aparece exatamente duas vezes nas listas de adjacência, uma na lista de

i

e uma na lista de

j

, e há

| E |

arestas. A lista de adjacência de um grafo direcionado contém um total de

| E |

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?

Entrar

Classificar por:

Nenhuma postagem por enquanto.

Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.