BFS x DFS x n ary tree
---
好吧還是第一次寫，遇到了其中有幾個問題，就是在二維陣列的時候走訪的時候，再以探索路徑的時候 顯示所有路徑，在 bfs搜尋目標的時候，第一次找到的時候 就已經是最短路徑，向 dfs 的話 就不一樣了，他是算 假設是有路的時候 就會往下一直走， 最後呢 我想直觀一點 用 nary 去把路徑給統計出來，好像是多此一舉(???。
# -*- coding: utf-8 -*-
"""
Created on Thu Apr 18 10:12:21 2019
@author: x213212
"""
import os
import time
import random
import numpy as np
__author__ = 'Minsuk Heo'
#matrix=[]
#matrix.append([])
#matrix.append([])
#matrix[0].append(3)
#matrix[0].append(5)
#matrix[0].append(6)
#matrix[0].append(7)
#matrix[0].append(8)
#matrix[1].append(4)
#matrix[1].append(5)
#matrix[1].append(3)
#matrix[1].append(2)
#matrix[1].append(3)
#print(matrix)
#決定陣列大小
width = 10
height = 10
# Python program to mirror an n-ary tree
# Represents a node of an n-ary tree
class Node :
# Utility function to create a new tree node
def __init__(self ,key):
self.key = key
self.child = []
# Function to convert a tree to its mirror
def mirrorTree(root):
# Base Case : nothing to do if root is None
if root is None:
return
# Number of children of root
n = len(root.child)
# If number of child is less than 2 i.e.
# 0 or 1 we don't need to do anything
if n <2 :
return
# Calling mirror function for each child
for i in range(n):
mirrorTree(root.child[i]);
# Reverse variable sized array of child pointers
root.child.reverse()
# Prints the n-ary tree level wise
def printNodeLevelWise(root,tmp,tmp2):
if root is None:
return
# create a queue and enqueue root to it
queue = []
queue.append(root)
# Do level order traversal. Two loops are used
# to make sure that different levels are printed
# in different lines
while(len(queue) >0):
n = len(queue)
max_n = len(queue)
while(n > 0) :
# Dequeue an item from queue and print it
p = queue[0]
queue.pop(0)
# if(str(p.key) == str(tmp) ):
# print ('在'+ str(max_n-n) +'找到了'+str(tmp))
# print (p.key, )
# Enqueue all children of the dequeued item
for index, value in enumerate(p.child):
queue.append(value)
if(str(value.key) == str(tmp) ):
# print ('sercher!')
p.child[index].child.append(tmp2)
return
# print ('tmp:' + str(n))
n -= 1
# print ("") # Seperator between levels
# Prints the n-ary tree level wise
def printNodeLevelWise2(root):
if root is None:
return
# create a queue and enqueue root to it
queue = []
queue.append(root)
# Do level order traversal. Two loops are used
# to make sure that different levels are printed
# in different lines
all_len = 0
while(len(queue) >0):
n = len(queue)
while(n > 0) :
# Dequeue an item from queue and print it
p = queue[0]
queue.pop(0)
# if(str(p.key) == str(tmp) ):
# print ('在'+ str(max_n-n) +'找到了'+str(tmp))
# print (p.key, )
print(str(p.key)+' ', end='')
# Enqueue all children of the dequeued item
for index, value in enumerate(p.child):
# if(str(value.key) == str(tmp) ):
## print ('sercher!')
# print (p.child[index].child.append(tmp2))
#
queue.append(value)
n -= 1
all_len+=1
print ("") # Seperator between levels
print (all_len)
def printNodeLevelWise3(root,tmp,start,tmp2,tmp3):
if root is None:
return
# create a queue and enqueue root to it
queue = []
queue.append(root)
# Do level order traversal. Two loops are used
# to make sure that different levels are printed
# in different lines
while(len(queue) >0):
n = len(queue)
max_n = len(queue)
while(n > 0) :
# Dequeue an item from queue and print it
p = queue[0]
queue.pop(0)
# if(str(p.key) == str(tmp) ):
# print ('在'+ str(max_n-n) +'找到了'+str(tmp))
# print (p.key, )
if(start ==tmp):
print (p.key)
if(len(tmp3)):
tmp3.append(p.key)
tmp2.append(tmp3)
tmp3 = []
return
# Enqueue all children of the dequeued item
for index, value in enumerate(p.child):
queue.append(value)
if(str(value.key) == str(tmp) ):
# print ('sercher!')
print (str (value.key)+' ', end='')
tmp3.append(value.key)
printNodeLevelWise3(root,p.key,start,tmp2,tmp3)
tmp3 = []
# print (p.child[index].child.append(tmp2))
n -= 1
# print ("")
# Driver Program
""" Let us create below tree
* 10
* / / \ \
* 2 34 56 100
* | / | \
* 1 7 8 9
"""
#
#def k(start, end,tmp , tmp2):
## if( len(tmp2 )) == 0)
## for x in tmp :
## if (x[0]==start):
## tmp2.append([x])
# flag_name = tmp[0][0]
# for x in tmp:
# count = 0
# count2 = 0
# value = 0
# for y in tmp2:
# for indey in y:
## if(indey == flag_name ):
### print (tmp2[count2])
## flag_bo =False
## for z in tmp2[count2]:
## if (x[1] == z):
## flag_bo = True
## if(flag_bo == False):
## tmp2[count2].append(x[1])
# if(x[0] !=flag_name):
#
# flag_name = x[0]
#
# if(x[0] == start):
# print (x[0])
# if(x[1] == end):
# tmp2[count2].append(x[1])
# else:
# tmp2[count2].append(flag_name)
# count2 +=1
#
def k2(start, end,tmp , tmp2):
# if( len(tmp2 )) == 0)
root = Node(start)
for x in tmp :
if (x[0]==start):
root.child.append(Node(x[1]))
for x in tmp:
printNodeLevelWise(root,x[0],Node (x[1]) )
test = []
test2 = []
printNodeLevelWise3(root ,end, start,test,test2)
test3 = [test[0]]
for x in test :
find_bool = False
for y in test3:
if (y == x ):
find_bool = True
if(find_bool == False):
test3.append(x)
print ('--------------------')
# test3.reverse()
for x in test3 :
print (x)
# flag_name = tmp[0][0]
# for x in tmp:
# count = 0
# count2 = 0
# value = 0
# for y in tmp2:
# for indey in y:
## if(indey == flag_name ):
### print (tmp2[count2])
## flag_bo =False
## for z in tmp2[count2]:
## if (x[1] == z):
## flag_bo = True
## if(flag_bo == False):
## tmp2[count2].append(x[1])
# if(x[0] !=flag_name):
#
# flag_name = x[0]
#
# if(x[0] == start):
# print (x[0])
# if(x[1] == end):
# tmp2[count2].append(x[1])
# else:
# tmp2[count2].append(flag_name)
# count2 +=1
# for index in x :
## print (index)
# for indey in y :
# find = False
#
#
# for z in range (0,len(tmp2[count2]),1):
# if (index == tmp2[count2][z] ):
# find = True
# print ('find')
#
## print ( tmp2[count2].index('1'))
# if(index == indey ):
# value = index
# print ( tmp2[count2])
# print (count2)
# tmp2[count2].append(tmp[count][1 ])
# break
#
# count +=1
# count2 +=1
# print ( tmp[count] , count )
# print ('sss')
# if (value >0 and tmp2[count].index(value) == -1):
# tmp2[count].append(value)
#vertexList = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
#edgeList = [(0,1), (1,2), (1,3), (3,4), (4,5), (1,6)]
#index = [i for i in range(len(edgeList))]
#np.random.shuffle(index)
new_edgeList = []
dept = [0*x for x in range(width * height)]
#for x in index :
# new_edgeList.append(edgeList [x])
#print (edgeList)
print (new_edgeList)
#創建一微陣列 VERTEXlIST
new_vertexList = []
#得到49個點
for x in range (0,width*height ,1) :
new_vertexList.append('t'+str(x))
new_vertexList.append('■')
#為點加上邊 49個點其實是 二微陣列 所以每七個代表一個維度
matrix = []
#創建二微陣列 後面要來顯示搜尋結果
count = 0
for x in range (0,width,1):
matrix.append([])
for y in range (0,height , 1 ):
if( random.randint(0,4) == 4):
matrix[x].append ('■')
else:
matrix[x].append ('t'+str(count))
count = count +1
print (matrix)
matrix2 =matrix3= matrix
#開始創建邊 相鄰串列
count =0
for x in range (0,width,1):
for y in range (0,height,1):
if( x - 1 >=0):
if( matrix[x-1][y] != '■'):
new_edgeList.append( (new_vertexList.index(matrix[x][y]), new_vertexList.index(matrix[x-1][y]) ))
if ( x + 1 <= width-1 ):
if( matrix[x+1][y] != '■'):
new_edgeList.append( (new_vertexList.index(matrix[x][y]), new_vertexList.index(matrix[x+1][y]) ))
if ( y - 1 >=0 ):
if( matrix[x][y-1] != '■'):
new_edgeList.append( (new_vertexList.index(matrix[x][y]), new_vertexList.index(matrix[x][y-1]) ))
if ( y + 1 <= height-1):
if( matrix[x][y+1] != '■'):
new_edgeList.append( (new_vertexList.index(matrix[x][y]), new_vertexList.index(matrix[x][y+1]) ))
count = count +1
print (new_edgeList)
print (len(new_edgeList))
print (new_edgeList)
print (new_vertexList)
edgeList = new_edgeList
vertexList = new_vertexList
record = []
record2 = []
#data = edgeList[index]
#test_list=[ [0] * 6 for i in range(6) ]
#matrix = []
#
##創建二微陣列 後面要來顯示搜尋結果
#for x in range (0,width,1):
# matrix.append([])
# for y in range (0,height , 1 ):
# matrix[x].append ((x,y))
graphs = (vertexList, edgeList)
def backtrace(parent, start, end):
path = [end]
while path[-1] != start:
path.append(parent[path[-1]])
path.reverse()
return path
def bfs(graph, start,find):
vertexList, edgeList = graph
visitedList = []
queue = [vertexList.index(start)]
adjacencyList = [[] for vertex in vertexList]
# fill adjacencyList from graph
for edge in edgeList:
adjacencyList[edge[0]].append(edge[1])
# print (str(edge[0])+','+str(edge[1]))
# print (adjacencyList)
# print (adjacencyList)
# print ('--------------------')
# print (graph)
# print ('--------------------')
# bfs
while queue:
# print (queue)
current = queue.pop()
for neighbor in adjacencyList[current]:
# if (vertexList[neighbor] != '■') :
if not neighbor in visitedList:
# 要開啟 請 註解掉下面其中一行
# queue.insert(0,neighbor) bfs 路徑
queue.append(neighbor) #dfs 路徑 開關
bool_flag = False
for tmp in record2 :
if(tmp == [current,neighbor]):
bool_flag = True
if (bool_flag == False) :
record2.append([current,neighbor])
# tx_tmp =record2[neighbor]
# record2[neighbor]= tx_tmp.append(current)
# 記錄每一步
visitedList.append(current)
record.append (current)
# 加快搜尋路徑
visitedList.append(current)
l2 = list(set(visitedList))
# l2.sort(key=l1.index)
visitedList = l2
for tmp in visitedList :
dept [tmp] = dept [tmp ] + 1
# 需要在這裡 增加動畫
#--------------------
os.system("cls")
print ("serachering ~")
# time.sleep(0.0001)
for z in visitedList:
if(z == 0):
matrix[0][0] = 'x'
elif(z != 0):
if(matrix[int(z/width)][int(z%width)] == vertexList[z] ):
matrix[int(z/width)][int(z%width)] = 'x'
#--------------------
#顯示矩陣
for show in matrix :
print (show)
#-------------------- 搜尋目標 找到就 break 關掉就是搜索權路徑
# if(vertexList[current] == find):
# print ('find!')
# break
# else :
# print ('no find!')
#--------------------
# print (current)
# print (visitedList)
print ('走訪路徑')
print ('--------------------')
# return visitedList
return visitedList
#for tmp in matrix :
# print (tmp)
#for x in bfs(graphs, 0,1):
# print (vertexList[x])
ret =bfs(graphs,'t33','t63')
for y in ret:
for x in range ( 0 , width , 1 ):
for y in range (0, height ,1 ):
if ( y == matrix2[x][y] ):
matrix2[x][y] =='x'
for show in matrix2 :
print (show)
#print (ret)
count =0
for x in range ( 0 , width , 1 ):
for y in range (0, height ,1 ):
matrix3[x][y] = dept[count]
count +=1
print ('--------------------')
for show in matrix3 :
print (show)
print (record2)
record3=[[33]]
print ('--------------------')
k2(vertexList.index('t33'),vertexList.index('t63'),record2,record3)
#record2 = list(set(record2 ))
#print (record2)
#print (record3)
#print (bfs(graphs,'t33','t63'))
#for x in bfs(graphs, 0,'t46'):
# print (vertexList[x])
#print(bfs(graphs, 0,'D'))
#print (matrix)
# 註解 快速清除
Comments