Warning
This page is located in archive. Go to the latest version of this course pages. Go the latest version of this page.

class GNode :
    def __init__ ( self , name , parent = None ):
        self.name = name
        self.parent = parent
 
def traverse ( node ) :
    result = []
    while node != None :
        result.append ( node.name )
        node = node.parent
        return result
 
 
def bfs ( graph , start , goal ) :
    # graph as list of neighbors
    # start , goal are names of vertices
    queue = [ GNode ( start ) ]
    known = {}
    known [ start ] = True
    while len ( queue ) > 0:
        actual = queue.pop (0)
        if actual.name == goal:
            path = traverse ( actual )
            return path [:: -1]
        if not actual.name in graph :
            continue
        for neighbor in graph [ actual.name ]:
            if not neighbor in known :
                known [ neighbor ] = True
                queue.append ( GNode ( neighbor , actual ) )
    return []
 
g = {}
g[0] = [1,2,3]
 
a = bfs(g,0,1)
print(a)

courses/b3b33alp/cviceni/faq/bfsprednaska.txt · Last modified: 2023/12/04 15:06 by vonasvoj