bfs

# -*- coding: utf-8 -*-
"""
Created on Thu Apr 18 10:12:21 2019

@author: x213212
"""
import os
import time
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 


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 = []
#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))
#為點加上邊 49個點其實是 二微陣列 所以每七個代表一個維度
matrix = []

#創建二微陣列 後面要來顯示搜尋結果
count = 0
for x in range (0,width,1):
    matrix.append([])
    for y in  range (0,height , 1 ):
        matrix[x].append ('t'+str(count))
        count = count +1
#開始創建邊 相鄰串列
count =0
for x in range (0,width,1):
    for y in range (0,height,1):
        if( x - 1 >=0):
            new_edgeList.append( (new_vertexList.index(matrix[x][y]), new_vertexList.index(matrix[x-1][y]) ))
        if ( x + 1 <= width-1 ):
             new_edgeList.append( (new_vertexList.index(matrix[x][y]), new_vertexList.index(matrix[x+1][y]) ))
        if ( y - 1 >=0 ):
             new_edgeList.append( (new_vertexList.index(matrix[x][y]), new_vertexList.index(matrix[x][y-1]) ))
        if ( y + 1  <= height-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
#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 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 not neighbor in visitedList:
                queue.insert(0,neighbor)
        visitedList.append(current)
# 需要在這裡 增加動畫
#--------------------
        os.system("cls")
        print ("serachering ~")
        time.sleep(0.0001)
        for  z in visitedList:
            if(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):
            break
        
            
#        print (current)
#        print (visitedList)
    
    return visitedList
#for tmp  in matrix :
#    print (tmp)
print ('--------------------')
#for x in bfs(graphs, 0,1):
#    print (vertexList[x])

print (bfs(graphs,'t99','t46'))
matrix_count =0


#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 = 20
height = 20 


#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 = []
#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,7) == 7):
            matrix[x].append ('■')
        else:
            matrix[x].append ('t'+str(count))
        count = count +1
print (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] == '■'):
                continue
            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] == '■'):
                continue
            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]  == '■'):
                continue
            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]  == '■'):
                continue
            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
#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 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)
                   
        visitedList.append(current)
        l2 =  list(set(visitedList))
        visitedList = l2
# 需要在這裡 增加動畫
#--------------------
        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):
            break
        
            
#        print (current)
#        print (visitedList)
    
    print ('走訪路徑')
    print ('--------------------')
    return visitedList
#for tmp  in matrix :
#    print (tmp)

#for x in bfs(graphs, 0,1):
#    print (vertexList[x])

print (bfs(graphs,'t0','t99'))


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


#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 = []
#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 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)
                   
#        記錄每一步
        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):
            break
        
            
#        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 (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 = 8
height = 8


#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)
                    record2[neighbor].append (current)
#                    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 (bfs(graphs,'t33','t63'))


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