changed 6 years ago  
Linked with GitHub

https://hwchang0417.wordpress.com/category/leetcode/

https://kopu.chat/2017/09/22/實作graph與dfs、bfs走訪/

https://kopu.chat/2017/09/22/實作graph與dfs、bfs走訪/

http://www.cs.nthu.edu.tw/~dr834314/STL/link-list.html

http://larry850806.github.io/2016/06/06/STL1/#stack

https://blog.csdn.net/helloworlddm/article/details/76785268

# -*- cding: 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 = 8
height = 8

def k(start, 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   ):
                    tmp2[count2].append(x[1])
                if(x[0] !=flag_name):
                    flag_name = x[0]
            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)
                    queue.append(neighbor)
                    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)
#--------------------
        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]]



k(vertexList.index('t33'),record2,record3)
print (record3)
#print (bfs(graphs,'t33','t63'))
#for x in bfs(graphs, 0,'t46'):
#    print (vertexList[x])
#print(bfs(graphs, 0,'D'))
#print (matrix)
# 註解 快速清除
#os.system("cls")

```pyhton
# -*- 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 ('--------------------')
    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)
#                    queue.append(neighbor)
                    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)
#-------------------- 搜尋目標
#        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)
# 註解 快速清除
Select a repo