BFS x DFS x n ary tree
好吧還是第一次寫，遇到了其中有幾個問題，就是在二維陣列的時候走訪的時候，再以探索路徑的時候 顯示所有路徑，在 bfs搜尋目標的時候 ，第一次找到的時候 就已經是最短路徑，向 dfs 的話 就不一樣了，他是算 假設是有路的時候 就會往下一直走， 最後呢 我想直觀一點 用 nary 去把路徑給統計出來，好像是多此一舉(???。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # -*- 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) | |
| # 註解 快速清除 |
