首页 > itarticle > bfs

bfs

admin 11月 14, 2020 0

Assumption

All vertices are reachable from the given vertex. We use the following graph.

Instruction

Construct a directed graph class with adjacency list representation.
Use a list to record states of all vertices with True for visited and False for unvisited.
Use a queue to store vertices to start in each inner loop.
Start from one given vertex to reach all vertices reachable.
When a vertex is reached, alter the corresponding element in the state list from False to True.
When the queue is empty, all vertices are reached.

Code in Python 3.5

from collections import defaultdict, deque


class :
    '''
    A class for directed graph, with a method BFS to do Broad First Search and a method addEdge to construct adjacency list.
    '''

    def __init__(self):
        
        self.graph = defaultdict(list)

    def __repr__(self):
        # function to demonstrate the adjacency list of the graph
        a_list = ''
        for k,v in self.graph.items():
            a_list += repr(k) + ': ' + repr(v) + 'n'
        return a_list

    def addEdge(self, l, r):
        # construct the adjacency list, add an edge to the graph
        self.graph[l].append(r)

    def BFS(self, start):
        # conduct BFS with a given start vertex and print it out
        visited = [False] * len(self.graph)
        queue = deque([])
        queue.append(start)
        visited[start] = True

        while queue:
            start = queue.popleft()
            for i in self.graph[start]:
                if visited[i] is False:
                    queue.append(i)
                    visited[i] = True
            if queue:
                print(start, end='=>')
            else:
                print(start)


if __name__ == '__main__':
    # create a graph given in the above diagram
    graph = Graph()
    graph.addEdge(0, 1)
    graph.addEdge(0, 2)
    graph.addEdge(1, 2)
    graph.addEdge(2, 0)
    graph.addEdge(2, 3)
    graph.addEdge(3, 3)
    # print the adjacency list
    print('the adjacency list of this graph: ')
    print(graph)
    print('BFS result with vertex 2 as start point:')
    graph.BFS(2)

Output

the adjacency list of this graph: 
0: [1, 2]
1: [2]
2: [0, 3]
3: [3]

2=>0=>3=>1

Reference