python实现dict版图遍历示例
#_*_coding:utf_8_
import sys
import os
class Graph():
def __init__(self, V, E):
self.V = V
self.E = E
self.visited = []
self.dict = {}
self.fd = open("input.txt")
def initGraph(self):
self.visited = [0 for i in range(self.V+1)]
for i in range(self.E):
f, t = map(int, self.fd.readline().split())
#f, t = map(int, sys.stdin.readline().split())
if self.dict.has_key(f)==False:
l = []
l.append(t)
self.dict[f] = l
else:
l = self.dict[f]
l.append(t)
self.dict[f] = l
def dfsGraph(self, src):
self.visited[src] = 1
print src ,
if self.dict.get(src): #self.dict[src]会出现异常
for u in self.dict[src]:
if self.visited[u]==0:
self.dfsGraph(u)
graph = Graph(6, 10)
graph.initGraph()
graph.dfsGraph(1)
1 2
1 3
1 4
3 2
2 6
4 3
3 5
4 5
6 5
3 6
1 2 6 5 3 4
相关推荐
-
Python基于回溯法子集树模板实现图的遍历功能示例
本文实例讲述了Python基于回溯法子集树模板实现图的遍历功能.分享给大家供大家参考,具体如下: 问题 一个图: A --> B A --> C B --> C B --> D B --> E C --> A C --> D D --> C E --> F F --> C F --> D 从图中的一个节点E出发,不重复地经过所有其它节点后,回到出发节点E,称为一条路径.请找出所有可能的路径. 分析 将这个图可视化如下: 本问题涉及到图,那首
-
Python基于回溯法子集树模板实现8皇后问题
本文实例讲述了Python基于回溯法子集树模板实现8皇后问题.分享给大家供大家参考,具体如下: 问题 8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 分析 为了简化问题,考虑到8个皇后不同行,则每一行放置一个皇后,每一行的皇后可以放置于第0.1.2.....7列,我们认为每一行的皇后有8种状态.那么,我们只要套用子集树模板,从第0行开始,自上而下,对每一行的皇后,遍历它的8个状态即可. 代码: ''' 8皇后问题 '''
-
python回溯法实现数组全排列输出实例分析
本文实例讲述了python回溯法实现数组全排列输出的方法.分享给大家供大家参考.具体分析如下: 全排列解释:从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列.当m=n时所有的排列情况叫全排列. from sys import stdout #code from http://www.jb51.net/ def perm(li, start, end): if(start == end): for elem in li: stdout.wr
-
Python使用回溯法子集树模板解决迷宫问题示例
本文实例讲述了Python使用回溯法解决迷宫问题.分享给大家供大家参考,具体如下: 问题 给定一个迷宫,入口已知.问是否有路径从入口到出口,若有则输出一条这样的路径.注意移动可以从上.下.左.右.上左.上右.下左.下右八个方向进行.迷宫输入0表示可走,输入1表示墙.为方便起见,用1将迷宫围起来避免边界问题. 分析 考虑到左.右是相对的,因此修改为:北.东北.东.东南.南.西南.西.西北八个方向.在任意一格内,有8个方向可以选择,亦即8种状态可选.因此从入口格子开始,每进入一格都要遍历这8种状态.
-
Python基于回溯法子集树模板解决0-1背包问题实例
本文实例讲述了Python基于回溯法子集树模板解决0-1背包问题.分享给大家供大家参考,具体如下: 问题 给定N个物品和一个背包.物品i的重量是Wi,其价值位Vi ,背包的容量为C.问应该如何选择装入背包的物品,使得放入背包的物品的总价值为最大? 分析 显然,放入背包的物品,是N个物品的所有子集的其中之一.N个物品中每一个物品,都有选择.不选择两种状态.因此,只需要对每一个物品的这两种状态进行遍历. 解是一个长度固定的N元0,1数组. 套用回溯法子集树模板,做起来不要太爽!!! 代码 '''0-
-
python数据结构之图深度优先和广度优先实例详解
本文实例讲述了python数据结构之图深度优先和广度优先用法.分享给大家供大家参考.具体如下: 首先有一个概念:回溯 回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到目标.但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为"回溯点". 深度优先算法: (1)访问初始顶点v并标记顶点v已访问. (2)查找顶点v的第一个邻接顶点w. (3)若顶点v的邻接顶点w存在,则继续执行:否则回
-
Python图算法实例分析
本文实例讲述了Python图算法.分享给大家供大家参考,具体如下: #encoding=utf-8 import networkx,heapq,sys from matplotlib import pyplot from collections import defaultdict,OrderedDict from numpy import array # Data in graphdata.txt: # a b 4 # a h 8 # b c 8 # b h 11 # h i 7 # h g
-
Python基于回溯法子集树模板解决数字组合问题实例
本文实例讲述了Python基于回溯法子集树模板解决数字组合问题.分享给大家供大家参考,具体如下: 问题 找出从自然数1.2.3.....n中任取r个数的所有组合. 例如,n=5,r=3的所有组合为: 1,2,3 1,2,4 1,2,5 1,3,4 1,3,5 1,4,5 2,3,4 2,3,5 2,4,5 3,4,5 分析 换个角度,r=3的所有组合,相当于元素个数为3的所有子集.因此,在遍历子集树的时候,对元素个数不为3的子树剪枝即可. 注意,这里不妨使用固定长度的解. 直接套用子集树模板.
-
python数据结构之图的实现方法
本文实例讲述了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': [
-
Python数据结构与算法之图结构（Graph）实例分析
本文实例讲述了Python数据结构与算法之图结构(Graph).分享给大家供大家参考,具体如下: 图结构(Graph)--算法学中最强大的框架之一.树结构只是图的一种特殊情况. 如果我们可将自己的工作诠释成一个图问题的话,那么该问题至少已经接近解决方案了.而我们我们的问题实例可以用树结构(tree)来诠释,那么我们基本上已经拥有了一个真正有效的解决方案了. 邻接表及加权邻接字典 对于图结构的实现来说,最直观的方式之一就是使用邻接列表.基本上就是针对每个节点设置一个邻接列表.下面我们来实现一个最简
-
Python基于回溯法子集树模板解决取物搭配问题实例
本文实例讲述了Python基于回溯法子集树模板解决取物搭配问题.分享给大家供大家参考,具体如下: 问题 有5件不同的上衣,3条不同的裤子,4顶不同的帽子,从中取出一顶帽子.一件上衣和一条裤子作为一种搭配,问有多少种不同的搭配? 分析 换个角度看,现有头.身.腿三个元素,每个元素都有各自的几种状态. 头元素有['帽1', '帽2', '帽3', '帽4']共4种状态,身元素有['衣1', '衣2', '衣3', '衣4', '衣5']共5种状态,腿元素有['裤1', '裤2', '裤3']共3种状