Representação de Grafos

Na seção anterior vimos os conceitos principais sobre grafos e também como eles podem ser visualizados. Nesta seção veremos como eles podem ser representados em um programa de computador.

Existem basicamente duas representações para grafos. A melhor representação depende do que desejamos fazer com o grafo e do quão denso ou esparso é o grafo.Grafos esparsos são grafos que possuem um pequeno número de arestas em relação ao número de vértices, ao passo que em grafos densos o número de arestas se aproxima do máximo de arestas possível.

A primeira representação é chamada matriz de adjacências, que nada mais é do que uma matriz de linhas e colunasLembre-se que estamos seguindo a convenção de que representa o número de vértices do grafo. em que se existe uma aresta do vértice para o vértice . Se estivermos representando um grafo não-direcionado e existir uma aresta entre os vértices e , então teremos tanto quanto . Em outras palavras, a matriz de adjacências que representa um grafo não-direcionado é simétrica. Nessa representação, o tempo gasto para determinar se um vértice é vizinho de um vértice é constante, pois basta verificarmos se é igual a .

Exemplo de grafo e sua matriz de adjacência.

A segunda representação é chamada lista de adjacências, e consiste de um arranjo (ou lista) com nodos em que contém a lista de vizinhos do vértice . Se o grafo for direcionado, os vizinhos de um vértice serão somente aqueles vértices para os quais existe uma aresta saindo de . Nessa representação, o tempo gasto para determinar se um vértice é vizinho de um vértice é proporcional ao grau de saída do vértice , ou seja, ao número de arestas que saem de .

Exemplo de grafo e sua lista de adjacência.

Se o grafo a ser representado for relativamente esparso, a lista de adjacências oferecerá uma representação mais compacta (econômica) do grafo porque ela conterá somente as conexões existentes entre vértices.

Representando Grafos em Python

Nesta seção veremos duas formar simples de representar grafos em Python. Uma delas, que chamamos de representação explícita, armazena os nomes dos vértices no próprio grafo. A outra, chamada representação implícita, assume que cada vértice possui um identificador inteiro, e faz referência aos vértices por meio desse identificador.

Antes de discutirmos as formas de representar grafos, convém esclarecermos como montamos o grafo em si. Em nossos exemplos, assumiremos que nos será fornecida uma lista uma lista com as ligações entre vértices (uma lista de arestas), a partir da qual criaremos os vértices e as arestas que os conectam. Nos exemplos abaixo, trabalharemos com a seguinte lista de arestas:

A B
B C
B D
C B
C E
D A
E B

Agora vejamos como representar, em Python, o grafo descrito pela lista de arestas acima.

Representação Explícita

De uma forma bem simples, podemos representar um grafo em Python assim:

grafo = { "A" : ["B"],
          "B" : ["C", "D"],
          "C" : ["B", "E"],
          "D" : ["A"],
          "E" : ["B"]
        }

O código acima representa o grafo como um dicionário de listas. Ele nos diz que existe uma aresta do vértice a para o vértice b, uma aresta do vértice b para os vértices c e d, e assim por diante. A figura abaixo mostra o gráfico representado pelo código acima.

Exemplo de grafo - Representação explícita.

Outra alternativa é representar o grafo como um dicionário de conjuntos. Na prática, muito pouca coisa muda em relação à representação acima, mas se usarmos um conjunto em vez de uma lista garantimos que não haverá arestas duplicadas entre dois nodos – algo que assumimos para todos os grafos com que trabalharemos nos exemplos.

Dado um grafo qualquer, precisamos realizar operações sobre ele. As operações mais comuns são obter a lista de vértices do grafo, a lista de arestas, verificar se existe uma aresta entre dois vértices, adicionar uma aresta entre dois vértices, etc. Abaixo criaremos uma classe Grafo na qual implementamos essas e outras operações.

from collections import defaultdict


class Grafo(object):
    """ Implementação básica de um grafo. """

    def __init__(self, arestas, direcionado=False):
        self._grafo = defaultdict(set)
        self._direcionado = direcionado
        self.adiciona_arestas(arestas)


    def get_vertices(self):
        """ Retorna a lista de vértices do grafo. """

        return list(self._grafo.keys())


    def get_arestas(self):
        """ Retorna a lista de arestas do grafo. """

        return [(k, v) for k in self._grafo.keys() for v in self._grafo[k]]


    def adiciona_arestas(self, arestas):
        """ Adiciona arestas ao grafo. """

        for u, v in arestas:
            self.adiciona(u, v)


    def adiciona(self, u, v):
        """ Adiciona uma ligação (aresta) entre os nodos 'u' e 'v'. """

        self._grafo[u].add(v)
        if not self._direcionado:
            self._grafo[v].add(u)


    def eh_conectado(self, u, v):
        """ Existe uma aresta entre os vértices 'u' e 'v'? """

        return u in self._grafo and v in self._grafo[u]


    def __str__(self):
        return '{}({})'.format(self.__class__.__name__, dict(self._grafo))

Alguns comentários sobre a implementação acima:

Vejamos como criar e imprimir um grafo.

# Cria a lista de arestas.
arestas = arestas = [('A', 'B'), ('B', 'C'), ('B', 'D'), ('C', 'B'), ('C', 'E'), ('D', 'A'), ('E', 'B')]

# Cria e imprime o grafo.
grafo = Grafo(arestas, direcionado=True)
print(grafo._grafo)
defaultdict(<class 'set'>, {'A': {'B'}, 'B': {'C', 'D'}, 'C': {'B', 'E'}, 'D': {'A'}, 'E': {'B'}})

Vejamos agora como usar algumas das funções da classe Grafo implementada acima.

print(grafo.get_vertices())
['A', 'B', 'C', 'D', 'E']
print(grafo.get_arestas())
[('A', 'B'), ('B', 'C'), ('B', 'D'), ('C', 'B'), ('C', 'E'), ('D', 'A'), ('E', 'B')]
print(grafo.eh_conectado('A', 'B'), grafo.eh_conectado('E', 'C'))
True False

Representação Implícita

A diferença entre a representação explícita e a implícita é que nesta cada vértice recebe automaticamente um identificador inteiro enquanto naquela o nome de um vértice é definido arbitrariamente. Vejamos um exemplo de grafo representado implicitamente.

grafo = [ [1],           # Vizinhos do vértice 0.
          [2, 3],        # Vizinhos do vértice 1.
          [1, 4],        # Vizinhos do vértice 2.
          [0],           # Vizinhos do vértice 3.
          [1]            # Vizinhos do vértice 4.
        ]

O grafo acima mostra uma representação equivalente à do grafo com o qual vínhamos trabalhando até agora (o vértice 0 é equivalente ao A, o vértice 1 ao B, e assim por diante). Veja abaixo uma figura ilustrando esse grafo.

Exemplo de grafo - Representação implícita.

Como exercício, veja se consegue adaptar a implementação da classe Grafo para essa nova representação. Aqui está uma sugestão de implementação.

from collections import defaultdict


class Grafo(object):
    """ Implementação básica de um grafo. """

    def __init__(self, arestas, num_vertices, direcionado=False):
        self._grafo = [ [] for _ in range(num_vertices) ]
        self._direcionado = direcionado
        self.adiciona_arestas(arestas)


    def get_vertices(self):
        """ Retorna a lista de vértices do grafo. """

        return list(range(len(self._grafo)))


    def get_arestas(self):
        """ Retorna a lista de arestas do grafo. """

        return [(u, v) for u in range(len(self._grafo)) for v in self._grafo[u]]


    def adiciona_arestas(self, arestas):
        """ Adiciona arestas ao grafo. """

        for u, v in arestas:
            self.adiciona(u, v)


    def adiciona(self, u, v):
        """ Adiciona uma ligação (aresta) entre os nodos 'u' e 'v'. """
        self._grafo[u].append(v)
        if not self._direcionado:
            self._grafo[v].append(u)



    def eh_conectado(self, u, v):
        """ Existe uma aresta entre os vértices 'u' e 'v'? """

        return v in self._grafo[u] if len(self._grafo) > u else -1


    def __str__(self):
        return '{}({})'.format(self.__class__.__name__, dict(self._grafo))

Veja abaixo como usar algumas das funções da classe Grafo.

# Cria a lista de arestas.
arestas = arestas = [(0, 1), (1, 2), (1, 3), (2, 1), (2, 4), (3, 0), (4, 1)]

# Cria e imprime o grafo.
grafo = Grafo(arestas, 5, direcionado=True)
print(grafo._grafo)
[[1], [2, 3], [1, 4], [0], [1]]

Vejamos agora como usar algumas das funções da classe Grafo implementada acima.

print(grafo.get_vertices())
[0, 1, 2, 3, 4]
print(grafo.get_arestas())
[(0, 1), (1, 2), (1, 3), (2, 1), (2, 4), (3, 0), (4, 1)]
print(grafo.eh_conectado(0, 1), grafo.eh_conectado(4, 2))
True False

Agora que já sabemos como representar grafos em Python, precisamos entender como criar algoritmos que operem sobre esses grafos.