Python版

https://github.com/faif/python-patterns/blob/master/other/graph_search.py

#!/usr/bin/env python

-*- coding: utf-8 -*-

""

class GraphSearch:

"""Graph search emulation in python, from source  
http://www.python.org/doc/essays/graphs/"""

def \_\_init\_\_(self, graph):  
    self.graph = graph

def find\_path(self, start, end, path=None):  
    path = path or \[\]

    path.append(start)  
    if start == end:  
        return path  
    for node in self.graph.get(start, \[\]):  
        if node not in path:  
            newpath = self.find\_path(node, end, path\[:\])  
            if newpath:  
                return newpath

def find\_all\_path(self, start, end, path=None):  
    path = path or \[\]  
    path.append(start)  
    if start == end:  
        return \[path\]  
    paths = \[\]  
    for node in self.graph.get(start, \[\]):  
        if node not in path:  
            newpaths = self.find\_all\_path(node, end, path\[:\])  
            paths.extend(newpaths)  
    return paths

def find\_shortest\_path(self, start, end, path=None):  
    path = path or \[\]  
    path.append(start)

    if start == end:  
        return path  
    shortest = None  
    for node in self.graph.get(start, \[\]):  
        if node not in path:  
            newpath = self.find\_shortest\_path(node, end, path\[:\])  
            if newpath:  
                if not shortest or len(newpath) < len(shortest):  
                    shortest = newpath  
    return shortest

example of graph usage

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

initialization of new graph search object

graph1 = GraphSearch(graph)

print(graph1.find_path('A', 'D'))
print(graph1.find_all_path('A', 'D'))
print(graph1.find_shortest_path('A', 'D'))

OUTPUT ###

['A', 'B', 'C', 'D']

[['A', 'B', 'C', 'D'], ['A', 'B', 'D'], ['A', 'C', 'D']]

['A', 'B', 'D']

Python转载版