2 qq 16723867 qq_16723867 于 2016.03.03 11:26 提问

python 广度优先搜索 遍历图中的点

mapmodel=[
[0,1,1,-1,1],
[1,0,-1,1,-1],
[1,-1,0,-1,1],
[-1,1,-1,0,-1],
[1,-1,1,-1,0]
]

flag=[1,0,0,0,0]

def dfs(current,sumpoint):

if sumpoint==5:
print sumpoint,flag
for i in range(5):
if mapmodel[current][i]==1 and flag[i]==0:
sumpoint=sumpoint+1
flag[i]=i
dfs(i,sumpoint)
return

dfs(0,1)

我想要遍历图里面的点,但总是得不到正确结果,不知道哪里出问题了,请大家指教

2个回答

u013596119
u013596119   Rxr 2016.03.05 18:37
已采纳

试下这个,flag和module和你上面的一样,然后dfs(0)

 def dfs(current):
    for i in range(5):
        if mapmodel[current][i]==1 and flag[i]==0:
            flag[i]=1
            print i,flag
            dfs(i)
qq_16723867
qq_16723867 是深度优先,不过写的时候很混乱。谢谢啦~
2 年多之前 回复
u013596119
u013596119   Rxr 2016.03.05 18:37

大哥,你这个是dfs,是深度优先啊?是要广度还是深度?

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
利用广度优先搜索求最短路径
注:下面是以无权的图为基础的 广度优先搜索:http://blog.csdn.net/u012763794/article/details/51081830 1.问题描述 输入: 输入n个顶点,m条边, 起点的编号 跟着再输入边x,y 输出: 该起点到达各个顶点最少经过几条边 样例: 输入: 5 5 2 1 2 2 3 2 4 3 4 3 5
图的遍历之广度优先搜索
广度优先搜索遍历类似于树的按层次遍历的过程。假设从图中某个顶点v出发,在访问了v之后依次访问v的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使用”先被访问的顶点的邻接点“先于”后被访问的顶点的邻接点“被访问,直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问,则选图中一个未被访问的节点作为起始点,重复上述过程,直至图中所有顶点都被访问到为止。若用邻
Python广度优先搜索得到两点间最短路径
前言之前一直写不出来,这周周日花了一下午终于弄懂了= =|| , 顺便放博客里,方便以后忘记了再看看 要实现的是输入一张 图,起点,终点,输出起点和终点之间的最短路径思路广度优先搜索是以层为顺序,将某一层上的所有节点都搜索到了之后才向下一层搜索; 比如下图: 从0结点开始搜索的话,顺序就是 0, 1,2,4, 3,这里用下划线表示每一层搜索得到的结点;因此,可以用一个队列来保存已经访问过的
算法7-6:图的遍历——广度优先搜索
题目描述 广度优先搜索遍历类似于树的按层次遍历的过程。其过程为:假设从图中的某顶点v出发,在访问了v之后依次访问v的各个未曾被访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问,直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作为起始点。重复上述过程,直至图中所有顶...
图的遍历(广度优先搜索遍历)
1、广度优先搜索遍历过程 (1)从某个顶点V出发,访问该顶点的所有邻接点V1,V2..VN (2)从邻接点V1,V2...VN出发,再访问他们各自的所有邻接点 (3)重复上述步骤,直到所有的顶点都被访问过 若此时图中还有顶点未被访问,则在外控算法的控制下,另选一个未曾被访问的顶点作为起始点,重复上述过程,直到图中所有顶点都被访问完为止。 2、示例 对图7-2
广度优先遍历解决最短路问题
BFS(广度优先遍历)在一般的带权图中是不能解决最短路问题,了解BFS的都知道,BFS是根据节点到源节点之间的节点数遍历的,也就是先访问离源节点节点数最少的点。要使得BFS能计算最短路径,需要图结构满足所有的权值相等。否则应该使用dijistra算法去解决最短路。权值相等的这种情况,在解决迷宫问题的时候有很好的表现能力。因为迷宫问题满足下面几个特点: 1.迷宫采用矩阵的方式去储存的时候,矩阵中的每
图(邻接表)的遍历——DFS(深度优先搜索)和BFS(广度优先搜索)和连通图
深度优先搜索(DFS)是一个不断探查和回溯的过程。在探查的每一步,算法都有一个当前顶点。————意味着要用递归咯。 最初的当前顶点就是指定的起始点。 每一步探查过程中,首先对当前顶点v进行访问,并立即设置该顶点的访问标志为true,表示该顶点已经被访问过。 接着在v的所有邻接顶点中找出尚未访问过的一个,将其视为下一步探查的当前顶点,直到所有顶点都被访问过。 核心代码: void DFS
JAVA广度优先搜索---寻找从A点到B点最短路径
前言搜索界两大基础搜索算法分别是广度优先搜索和深度优先搜索。搜索算法可以用于寻找图的连通性。 一个普通的二维地图,从A点到B点,有两个问题。 能否到达? 怎样以最短的路径走到B点? 这是搜索算法能够解决的事情。要使用广度优先搜索算法来搜索从A点到B点的最短路径依据广度优先的原则,每走一步,都将下一步所有可能的选择入队之后,才进行下一步结束标记:队列为空时,搜索结束 搜索到指定结果时,搜索结束实
图的遍历——广度优先搜索
题目描述 广度优先搜索遍历类似于树的按层次遍历的过程。其过程为:假设从图中的某顶点v出发,在访问了v之后依次访问v的各个未曾被访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问,直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作为起始点。重复上述过程,直至图中所有
邻接矩阵的广度优先搜索
广度优先搜索遍历类似于树的按层次遍历的过程。操作步骤: 假设从图中某顶点v出发,在访问了v之后一次访问v的各个未曾访问过的邻接点,然后分别从这些邻接点出发一次访问他们的邻接点,并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻结点”被访问,直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作为起始点,,重复上述过程,直至所有顶点都被访问到为