Pythonデータ構造実装図

図
図は、エッジまたはアークで接続されたノードのネットワークです.有向図では,ノード間の接続に方向があり,アーク(arcs)と呼ばれる.無方向図では,ノード間の接続に方向がなく,エッジ(edge)と呼ぶ.図アルゴリズムは、2点間経路、2点間最短経路、1つの図にループが存在するか否かを判断する(ループは、1つのノードから1つの非空経路に沿ってそれ自体に戻ることができる)、すべてのノードを遍歴できる経路を見つける(有名なTSP問題、すなわち旅行業者問題)などを含む.
図の実装
Pythonでは,図は主にリストと辞書で構成されている.例えば次の図は

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

次の辞書とリストを組み合わせて構築します

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

ソースコード

# -*- encoding:utf-8 -*-
'''

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

'''


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 path

def find_all_paths(graph, start, end, path=[]):
        '       '
        path = path + [start]
        if start == end:
            return [path]
        if not graph.has_key(start):
            return []
        paths = []
        for node in graph[start]:
            if node not in path:
                newpaths = find_all_paths(graph, node, end, path)
                for newpath in newpaths:
                    paths.append(newpath)
        return paths

def find_shortest_path(graph, start, end, path=[]):
        '      '
        path = path + [start]
        if start == end:
            return path
        if not graph.has_key(start):
            return None
        shortest = None
        for node in graph[start]:
            if node not in path:
                newpath = find_shortest_path(graph, node, end, path)
                if newpath:
                    if not shortest or len(newpath) < len(shortest):
                        shortest = newpath
        return shortest

#test

if __name__ == '__main__':
    graph = {'A': ['B', 'C'],
             'B': ['C', 'D'],
             'C': ['D'],
             'D': ['C'],
             'E': ['F'],
             'F': ['C']}
    print find_path(graph,'A','D')
    print find_all_paths(graph,'A','D')
    print find_shortest_path(graph,'A','D')