Python实现简单的图算法 - 1
#coding=utf8
import re
import requests
import os, sys
import json
import linecache
import util
import time
import datetime
import zipfile
import shutil
import time
import time
import traceback
import math
import logging
global g_count
g_count = 0
class Solution(object):
def __init__(self):
# 当前文件的路径
self.current_path = os.getcwd()
print("Current Path => ",self.current_path)
#获取logger实例,如果参数为空则返回root logger
self.logger = logging.getLogger("map")
#执行logger输出格式
formatter = logging.Formatter('%(asctime)s %(levelname)-8s: %(message)s')
#文件日志
logfile = "%s/%s"%(self.current_path,"map.log")
print("Current Log File Path => ", logfile)
file_handler = logging.FileHandler(logfile)
file_handler.setFormatter(formatter)
#控制台日志
console_handler = logging.StreamHandler(sys.stdout)
console_handler.formatter = formatter
#为logger添加的日志处理器
self.logger.addHandler(file_handler)
self.logger.addHandler(console_handler)
#指定日志的最低输出级别,默认为info级别
self.logger.setLevel(logging.INFO)
def find_path(self,graph,start,end,path=[]):
global g_count
g_count += 1
print str(g_count) + " find_path .... "
path = path + [start]
print 'path = ',path
if start == end:
return path
if not graph.has_key(start):
return None
for node in graph[start]:
if node not in path:
newpath = Test.find_path(graph,node,end,path)
if newpath:
return newpath
return None
def find_all_paths(self,graph,start,end,path=[]):
path = path + [start]
if start == end:
path.append( " * ") #标记下找到了节点
return path
if not graph.has_key(start):
return []
paths = []
for node in graph[start]:
if node not in path:
newpaths = Test.find_all_paths(graph,node,end,path)
print "final newpaths = ",newpaths
for newpath in newpaths:
paths.append(newpath)
#paths.append(" * ")
return paths
def find_shortest_path(self,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 = Test.find_shortest_path(graph, node, end, path)
if newpath:
if not shortest or len(newpath) < len(shortest):
shortest = newpath
return shortest
'''
A -> B
A -> C
B -> C
B -> D
C -> D
D -> C
E -> F
F -> C
'''
if __name__ == '__main__':
#用字典和列表来构建
graph = {
'A':['B','C'],
'B':['C','D'],
'C':['D'],
'D':['C'],
'E':['F'],
'F':['C']
}
Test = Solution()
path = []
path = Test.find_path(graph,'A','C',path)
print '某一条路径 => ',path
path = []
paths = Test.find_all_paths(graph,'A','C',path)
print '全部路径 => ',paths
shortest_path = Test.find_shortest_path(graph,'A','C',path)
print '最短的路径 = ',shortest_path