[SP-pm] Distância entre nós em um grafo

[Carlos Costa]

Oi Blabos,

Não use cpan pra um problema simples, grafos são facilmente representados
como Adjacency Lists ( http://en.wikipedia.org/wiki/Adjacency_list ) em
Perl: basicamente uma hash table onde cada vertex aponta para uma lista de
vertices adjacentes.

Aqui tem uma explicação bem elegante (e traduzível pra Perl)
http://www.python.org/doc/essays/graphs/
Basicamente o grafo:

    A -> B
    A -> C
    B -> C
    B -> D
    C -> D
    D -> C
    E -> F
    F -> C

Vai virar algo assim:

graph = {'A': ['B', 'C'],
         'B': ['C', 'D'],
         'C': ['D'],
         'D': ['C'],
         'E': ['F'],
         'F': ['C']}

Depois é so criar uma função que encontre o caminho entre dois nós:

    def find_path(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return path
        if not graph.has_key(start):
            return None
        for node in graph[start]:
            if node not in path:
                newpath = find_path(graph, node, end, path)
                if newpath: return newpath
        return None


E rodar o código:

    >>> find_path(graph, 'A', 'D')
    ['A', 'B', 'C', 'D']

O tamanho do array retornado por find_path() vai ser o número que você
procura.

( )s
Carlos.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.pm.org/pipermail/saopaulo-pm/attachments/20130920/2d39d6b6/attachment.html>