def get_index(i, j, G): num = 0 for a in xrange(i): num += G[a].count('0') for b in xrange(j): if G[i][b] == '0': num += 1 return i * len(G) + j - num def get_graph(G): G = [list(x) for x in G] EG = [] for i in xrange(len(G)): for j in range(len(G[i])): if G[i][j] == '0': continue side_list = [] if j+1 <=len(G[i]) -1: ifG[i][j+1] == '1': index = get_index(i,j+1, G) side_list.append(index) ifj-1 >= 0: if G[i][j-1] == '1': index = get_index(i, j-1, G) side_list.append(index) if i+1 <=len(G) -1: ifG[i+1][j] == '1': index = get_index(i+1,j, G) side_list.append(index) ifi-1 >= 0: if G[i-1][j] == '1': index = get_index(i-1, j, G) side_list.append(index) EG.append(side_list) return EG
而算法的实现用图的邻接矩阵则更为方便,因此我写了一个将上列二位列表转换成邻接矩阵形式的函数:
defget_matrix(graph): result = [[0]*len(graph) for
_ in xrange(len(graph))] # 初始化 for i in xrange(len(graph)): for j in graph[i]: result[i][j] = 1# 有边则为1 return result
主要的 DFS 算法如下:
# graph为图的邻接矩阵 used为已访问栈 path为路径栈 step为已经遍历的顶点的个数 defdfs(graph, path, used, step): if step == len(graph): # 判断顶点是否被遍历完毕 print path returnTrue else: for i in xrange(len(graph)): ifnot used[i] and graph[path[step-1]][i] == 1: used[i] = True path[step] = i if dfs(graph, path, used, step+1): returnTrue else: used[i] = False# 回溯 返回父节点 path[step] = -1 returnFalse defmain(graph, v): used = [] # 已访问栈 path = [] # 路径栈 for i
in xrange(len(graph)): used.append(False) # 初始化 所有顶点均未被遍历 path.append(-1) # 初始化 未选中起点及到达任何顶点 used[v] = True# 表示从起点开始遍历 path[0] = v # 表示哈密顿通路的第一个顶点为起点 dfs(graph, path, used, 1)
完整代码如下:
#! /usr/bin/env python # -*- coding: utf-8 -*- # Coding with love by Naiquan. defdfs(graph, path, used, step): if step == len(graph): print path returnTrue else: for i in xrange(len(graph)): ifnot used[i] and graph[path[step-1]][i] == 1: used[i] = True path[step] = i if dfs(graph, path, used, step+1): returnTrue else: used[i] = False path[step] = -1 returnFalse defmain(graph, v): used = [] path = [] for i in xrange(len(graph)): used.append(False) path.append(-1) used[v] = True
path[0] = v dfs(graph, path, used, 1) defget_index(i, j, G): num = 0 for a in xrange(i): num += G[a].count('0') for b in xrange(j): if G[i][b] == '0': num += 1 return i * len(G) + j - num defget_graph(G): G = [list(x) for x in G] EG = [] for i in xrange(len(G)): for j in range(len(G[i])): if G[i][j] == '0': continue side_list = [] if j+1 <= len(G[i]) - 1: if G[i][j+1] == '1': index = get_index(i, j+1, G) side_list.append(index) if j-1 >= 0: if G[i][j-1] == '1': index = get_index(i, j-1, G) side_list.append(index) if i+1 <= len(G) - 1: if G[i+1][j] == '1': index = get_index(i+1, j, G) side_list.append(index) if i-1 >= 0: if G[i-1][j] == '1': index = get_index(i-1, j, G) side_list.append(index) EG.append(side_list) return EG defget_matrix(graph): result = [[0]*len(graph) for _ in xrange(len(graph))] for i in xrange(len(graph)): for j in graph[i]: result[i][j] = 1 return result if __name__ == '__main__': map_list = [ '111111', '101101', '111111', '101101', '111111', '000000' ] G = get_graph(map_list) map_matrix = get_matrix(G) # print map_matrix SP = 14 main(map_matrix, SP)